フィボナッチ数

概要
フィボナッチ数は次の再起関係で定義されます。
 F(1)=F(2)=1,
 F(n)=F(n-1)+F(n-2)  n≧3の時、

一般解
フィボナッチ数の一般解は次のように計算できます。証明は数学的帰納法で行います。


F(0)=0,F(1)=1;

組み合わせ数
 これを、組み合わせで考えますと、全部1段づつ上る場合(2段とびなし)は1通りで nC0、一度だけ2段上がる場合は n-1C1
2度2段上がりする場合、n-2C2となります。
 したがって、次の関係が成立します。
 F(n)=Σ(p=0,(n-1)/2)n-pCp
 たとえば、F(6) = 6C0 + 5C1 + 4C2 + 3C3 です。

階段の昇り方
n段の階段を1段、または2段で上がる方法はフィボナッチ数になります。n段を上がるには、(n-1)段を上り最後に1段上るか、(n-2)昇り最後に2段を上ることになります。したがって、n段上がり型は
   F(n) = F(n-1) + F(n-2)
 となります。