フィボナッチ数列と「階段上り」2

パスカルの三角形に「階段」を設定しみよう。
　　
左側の１は間隔1で並んでいるとする。右側の１は間隔2で並んでいるとする。階段は左側を下、右側を上として、同じ数字同士（3と3,4と4など）をつなぐ。右側は2の間隔だから、数字1の間に階段の上部がくる場合がある。次のようになる。

右の青い数字がフィボナッチ数列である。
　　　1, 1, 2, 3, 5, 8, 13, 21, …
「何段あっても、最後が1段で上るときの場合の数は「前回の場合の数」となり、最後を2段で上るときは「前々回の場合の数」となり、その合計が着目している階段の上り方の場合の数となる。」これは上の数列で3＋5＝8、5＋８＝13など確認できる。

もう少し立ち入ってみよう。
フィボナッチ数列の項を、パスカルの三角形の要素で表わすと次のようになる。
1 ＝ ₀C₀
1 ＝ ₁C₀
2 ＝ ₂C₀＋₁C₁
3 ＝ ₃C₀＋₂C₁
5 ＝ ₄C₀＋₃C₁＋₂C₂
8 ＝ ₅C₀＋₄C₁＋₃C₂
13＝₆C₀＋₅C₁＋₄C₂＋₃C₃
……
Cで表示すると、階段は、左下添え字が1つずつ減り、右下添え字が1つずつ増えていく過程に対応しているとわかる。
これがどうしてフィボナッチ数列になるかといえば、パスカルの三角形が、
　_nC_r＝_n－1C_r－1＋_n－1C_r
という規則で並べられているからである。nに対して、２つのn－1が、１つ前の「階段」と、２つ前の「階段」に位置していることによっている。全体の関係が、それを構成する要素においても成立していることによっている。

3,5,8で確認してみよう。
3＝　　 ₃C₀＋₂C₁
＋　　　＋　＋
5＝₄C₀＋₃C₁＋₂C₂
　　↓　　↓　　↓　　₃C₀＋₃C₁＝₄C₁　,　₂C₁＋₂C₂＝₃C₂　,　₄C₀＝₅C₀
8＝₅C₀＋₄C₁＋₃C<sub>2

3</sub>C₀（2つ前の階段）＋₃C₁（1つ前）＝₄C₁　,　₂C₁（2つ前）＋₂C₂（1つ前）＝₃C₂　,　₄C₀（1つ前、2つ前は0）＝₅C₀

5,8,13でも確認しておこう。
5 ＝　　 ₄C₀＋₃C₁＋₂C₂
＋　　　 ＋　　＋　　
8 ＝ ₅C₀＋₄C₁＋₃C₂
　　　↓　 ↓　　↓　　↓　₄C₀＋₄C₁＝₅C₁　,　₃C₁＋₃C₂＝₄C₂　,　₅C₀＝₆C₀　,　₂C₂＝₃C₃
13＝₆C₀＋₅C₁＋₄C₂＋₃C₃

こんどは一般的な階段、フィボナッチ数列の一般項についてみておこう。

フィボナッチ数列の項のいくつかをCを使って表示すると、次のようになった。
5 ＝ ₄C₀＋₃C₁＋₂C₂
8 ＝ ₅C₀＋₄C₁＋₃C₂
13＝₆C₀＋₅C₁＋₄C₂＋₃C₃

左下添え字が1つずつ減り、右下添え字が1つずつ増えている。どこで終わるかといえば、_nC_rのnの半分程度で終わるが、偶数か奇数かによって区別される。rに着目して、区別してみよう。左下添え字が偶数の場合、nとrは同じ値で終わる（₂C₂、₃C₃）。それはn/2にあたる。奇数の場合、nとrは異なる値（₃C₂）でrは1だけ小さい。これをガウス記号[　]（ある値を超えないもっとも大きな整数）を用いると、偶数と奇数の場合を統一して把握できる。[4/2]＝2、[6/2]＝3、[5/2]＝2が最終項のrの値である。パスカルの三角形に出てくるフィボナッチ数列の一般項Fnは
　　　Fn＝_nC₀＋_n－1C₁＋_n－2C₂＋……＋_n－[n/2]C_[n/2]
となる。

注　図は「やまでぃーのブログ」を拝借した。