原点(0,0)から、直線x+2y=n上の格子点への道の個数はFn+1に等しい。

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

n=7の場合、

(7,0)までの道の個数=1

(5,1)までの道の個数=6

(3,2)までの道の個数=10

(1,3)までの道の個数=4

1+6+10+4=21=f8

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

この問題は下記の問題と本質的に等しい

　ｎ枚の畳を鰻の寝床のように細長いｎ×２の間取りに敷くその敷き方の数は，半畳の正方形の１辺を単位として数えると，ｎを１と２に分割する組み合わせ数（ｎ段の階段を一歩で１段または２段昇ることにする昇り方の数）に一致する．

　それは

　　Ｆn＝Ｆn-1＋Ｆn-2

の関係になるから，フィボナッチ数列（初項１，第２項２）

　　１，２，３，５，８，１３，２１，３４，５５，８９，・・・

　　Ｆn＝１／√５［｛（１＋√５）／２｝^n+1−｛（１−√５）／２｝^n+1］

が現れることになる．

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝