【２】フィボナッチ数とパスカルの三角形

　パスカルの三角形では先頭と最後が常に１となり，その間の数値は前の行の連続した数値を加えていくことに得られる．一方，フィボナッチ数は前２項の和と等しい．どちらも再帰的（同じ規則を反復的に実行する）というわけである．

　パスカルの三角形になだらかな斜線を引いて，斜線上に並ぶ数の和をとればフィボナッチ数が順番に現れる．

　　１＋１＝２，１＋２＝３，１＋３＋１＝５，１＋４＋３＝８，１＋５＋６＋１＝１３，・・・

　パスカルの三角形とフィボナッチ数の関係は古くから知られていたが，

　　ｆn＝Σ（ｎ−ｋ，ｋ）

はその二項係数表現になっている．

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

ｆ0＝（0，0）＝1

ｆ1＝（1，0）＝1

ｆ2＝（2，0）+（1，1）＝2

ｆ3＝（3，0）+（2，1）＝3

ｆ4＝（4，0）+（3，1）+（2，2）＝5

ｆ5＝（5，0）+（4，1）+（3，2）＝8

ｆ6＝（6，0）+（5，1）+（4，2）+（3，3）＝13

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

しかし、これらは

（その３３）：14=(5,3)+(3,2)+(1,1)

（その３５）：７＝（４，３）＋（３，２）＋（０，１）、１０＝（４，２）＋（３，１）＋（０，０）

のようには変形できない

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

以下のようには変形できる

　　ｆn＝Σ（ｎ−ｋ，n-2k）

ｆ0＝（0，0）＝1

ｆ1＝（1，0）＝1

ｆ2＝（2，2）+（1，1）＝2

ｆ3＝（3，3）+（2，1）＝3

ｆ4＝（4，4）+（3，2）+（2，0）＝5

ｆ5＝（5，5）+（4，3）+（3，1）＝8

ｆ6＝（6，6）+（5，4）+（4，2）+（3，0）＝13

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

したがって、

ｆ5＝（5，5）+（4，3）+（3，2）＝8

ｆ7＝ｆ5+ｆ6＝（6，6）+（5，5）+（5，4）+（4，3）+（4，2）+（3，1）+（3，0）＝21

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