パスカルの三角形に「階段」を設定しみよう。

左側の1は間隔1で並んでいるとする。右側の1は間隔2で並んでいるとする。階段は左側を下、右側を上として、同じ数字同士(3と3,4と4など)をつなぐ。右側は2の間隔だから、数字1の間に階段の上部がくる場合がある。次のようになる。

右の青い数字がフィボナッチ数列である。
1, 1, 2, 3, 5, 8, 13, 21, …
「何段あっても、最後が1段で上るときの場合の数は「前回の場合の数」となり、最後を2段で上るときは「前々回の場合の数」となり、その合計が着目している階段の上り方の場合の数となる。」これは上の数列で3+5=8、5+8=13など確認できる。
もう少し立ち入ってみよう。
フィボナッチ数列の項を、パスカルの三角形の要素で表わすと次のようになる。
1 =
0C
0
1 =
1C
0
2 =
2C
0+
1C
1
3 =
3C
0+
2C
1
5 =
4C
0+
3C
1+
2C
2
8 =
5C
0+
4C
1+
3C
2
13=
6C
0+
5C
1+
4C
2+
3C
3
……
Cで表示すると、階段は、左下添え字が1つずつ減り、右下添え字が1つずつ増えていく過程に対応しているとわかる。
これがどうしてフィボナッチ数列になるかといえば、パスカルの三角形が、
nC
r=
n-1C
r-1+
n-1C
r
という規則で並べられているからである。nに対して、2つのn-1が、1つ前の「階段」と、2つ前の「階段」に位置していることによっている。全体の関係が、それを構成する要素においても成立していることによっている。
3,5,8で確認してみよう。
3=
3C
0+
2C
1
+ + +
5=
4C
0+
3C
1+
2C
2
↓ ↓ ↓
3C
0+
3C
1=
4C
1 ,
2C
1+
2C
2=
3C
2 ,
4C
0=
5C
0
8=
5C
0+
4C
1+
3C
2
3C
0(2つ前の階段)+
3C
1(1つ前)=
4C
1 ,
2C
1(2つ前)+
2C
2(1つ前)=
3C
2 ,
4C
0(1つ前、2つ前は0)=
5C
0
5,8,13でも確認しておこう。
5 =
4C
0+
3C
1+
2C
2
+ + +
8 =
5C
0+
4C
1+
3C
2
↓ ↓ ↓ ↓
4C
0+
4C
1=
5C
1 ,
3C
1+
3C
2=
4C
2 ,
5C
0=
6C
0 ,
2C
2=
3C
3
13=
6C
0+
5C
1+
4C
2+
3C
3
こんどは一般的な階段、フィボナッチ数列の一般項についてみておこう。
フィボナッチ数列の項のいくつかをCを使って表示すると、次のようになった。
5 =
4C
0+
3C
1+
2C
2
8 =
5C
0+
4C
1+
3C
2
13=
6C
0+
5C
1+
4C
2+
3C
3
左下添え字が1つずつ減り、右下添え字が1つずつ増えている。どこで終わるかといえば、
nC
rのnの半分程度で終わるが、偶数か奇数かによって区別される。rに着目して、区別してみよう。左下添え字が偶数の場合、nとrは同じ値で終わる(
2C
2、
3C
3)。それはn/2にあたる。奇数の場合、nとrは異なる値(
3C
2)でrは1だけ小さい。これをガウス記号[ ](ある値を超えないもっとも大きな整数)を用いると、偶数と奇数の場合を統一して把握できる。[4/2]=2、[6/2]=3、[5/2]=2が最終項のrの値である。パスカルの三角形に出てくるフィボナッチ数列の一般項F
nは
F
n=
nC
0+
n-1C
1+
n-2C
2+……+
n-[n/2]C
[n/2]
となる。
注 図は「やまでぃーのブログ」を拝借した。