SICP読書録その4

SICP

ex1.13

\phi=\frac{1+\sqrt{5}}{2}として、Fib(n)が\frac{\phi^n}{\sqrt{5}}に最も近い整数であることを証明せよ。


最初からヒントを当てにする。
つまり、\psi=\frac{1-\sqrt{5}}{2}として、Fib(n)=\frac{\phi^n-\psi^n}{\sqrt{5}}であることを帰納法によって証明する。


まず、n=0のとき。
Fib(0)=\frac{1-1}{2}=0 (1)


n=1のとき、
Fib(1)=\frac{(1+\sqrt{5})-(1-\sqrt{5})}{2\sqrt{5}}=1 (2)


つぎに、
Fib(n)=\frac{\phi^2-\psi^2}{\sqrt{5}}
と仮定する。(3)

このとき、Fib(n+1)を求めると次式のようになる(計算は省略)
Fib(n+1)=\frac{Fib(n)}{2}+\frac{\phi^n+\psi^n}{2}
また、Fib(n-1)を求めると次式のようになる。
Fib(n-1)=\frac{-Fib(n)}{2}+\frac{\phi^n+\psi^n}{2}
したがって、
Fib(n)+Fib(n-1)=\frac{Fib(n)}{2}+\frac{\phi^2+\psi^n}{2}=Fib(n+1) (4)


(1)〜(4)から、数学的帰納法よりFib(n)=\frac{\phi^n-\psi^n}{\sqrt{5}}//


順番が逆だけど、Fib(n)=\frac{\phi^n-\psi^n}{\sqrt{5}}を証明すればよいのは何でかを考える。

nが大きいほど\psi^nは振動しながら0に収束していくので、Fib(n)=\frac{\phi^n-\psi^n}{2}であれば、Fib(n)がFib(n)=\frac{\phi^n}{\sqrt{5}}に最も近い整数となるのは分かるんだけど、なんで\psiなんだろうなぁ？
そもそも、Fib(n)=\frac{\phi^n-\psi^n}{\sqrt{5}}をどこから導いたんだろうか？
なんか、よくわからんな。


また考えてみよう。保留。