概要
フィボナッチ数は次の再起関係で定義されます。
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)
となります。