問題1.13, p.23

Finnonacci数列の\(n\)番目の数を出力する関数を\(F(n)\)と書く。\(\phi = \frac{1 + \sqrt{5}}{2}\),\(\psi = \frac{1 - \sqrt{5}}{2}\)としたときに\(F(n) = \frac{ \phi^{n} - \psi ^{n} }{ \sqrt{5} }\)であることを示す。

帰納法の基底部。\(F(0)\)\(F(1)\)のとき主張が正しいことを計算して確かめる。

帰納法の仮定。\(F(n - 2)\),\(F(n - 1)\)のときに主張は正しいと仮定する。

帰納法のステップ。帰納法の仮定が成立するとき、\(F(n)\)のときも正しくなることを示す。Fibonacci数列の定義から、\(F(n) = F(n - 2) + F(n - 1) = \frac{\phi ^ {n - 1} - \psi ^ {n - 1}}{ \sqrt{5}} + \frac{\phi ^ {n - 2} - \psi ^ {n - 2}}{ \sqrt{5}}\)\(\phi ^ {n - 2} (\phi + 1) = \phi^{n - 1} + \phi^{n - 2}\)(\(\psi\)についても同様) と、\(\phi^{2} = \phi + 1\)(\(\psi\)についても同様 ) を使い式を展開すれば、\(F(n) = \frac{\phi ^ {n} - \psi ^ {n}}{ \sqrt{5}}\)を得る。