問題1.13

SICP 証明

gabuchan : 「さあ、証明するのだ」
babanban : 「yes master」


証明スタート
\phi = (1 + \sqrt{5})/2, \psi = (1 - \sqrt{5})/2 として
Fib(n) = (\phi^{n} - \psi^{n})/\sqrt{5}が０を含む全ての自然数について成り立つことをnに関する数学的帰納法をつかって証明する。
基底
n = 0 のとき
Fib(0) = 0
(\phi^{0} - \psi^{0})/\sqrt{5} = 0 より成り立つ
n = 1 のとき
Fib(1) = 1
(\phi^{1} - \psi^{1})/\sqrt{5} = 1 より成り立つ
帰納段階
Fib(n) = Fib(n-1) + Fib(n-2)
ここで帰納法の仮定を使って
Fib(n-1) = (\phi^{n-1} - \psi^{n-1})/\sqrt{5}
Fib(n-2) = (\phi^{n-2} - \psi^{n-2})/\sqrt{5}
がいえる。
Fib(n)
= Fib(n-1) + Fib(n-2)
= \frac{\phi^{n-1} - \psi^{n-1}}{\sqrt{5}} + \frac{\phi^{n-2} - \psi^{n-2}}{\sqrt{5}}
= \frac{\phi^{n-2}(\phi + 1) - \psi^{n-2}(\psi + 1)}{\sqrt{5}
( \phi^{2} = \phi + 1, \psi^{2} = \psi + 1 より)
= \frac{\phi^{n-2}*\phi^{2} - \psi^{n-2}*\psi^{2}}{\sqrt{5}}
= \frac{\phi^{n} - \psi^{n}}{\sqrt{5}}
よって成り立つ
証明終了

（一口メモ）
今回は帰納法の仮定を使うときにn-1とn-2が必要になるので基底ではn=0とn=1の２つの場合が成り立つことを証明しなくちゃいけない。