SICP 練習問題 1.13 （Fibonacci数の帰納的証明？）

練習問題 1.13は、普通に数学の問題なんじゃ。。
ちなみに命題の前半は、どう表現すればよいのかさっぱりわかりません！
なので、ヒント以降を証明しよう。


【問題】

φ = (1 + √5)) / 2

として、Fib(n)が (φ^n) / √5) に最も近い整数であることを証明せよ。

ヒント：

ψ = (1 - √5)) / 2

とする。帰納法とFibonacci数の定義(1.2.2節参照）を用い、

Fib(n) = (φ^n - ψ^n) / 5^(1/2)

を証明せよ。


【解答】
φとψの特性として、次が成り立つ。

φ^2 = φ + 1
ψ^2 = ψ + 1

また、初期条件として、n=0、n=1のケースを考える。

Fib(0) = (φ^0 - ψ^0) / √5
       = (0 - 0) / √5
       = 0

Fib(1) = (φ^1 - ψ^1) / √5)
       = (φ - ψ) / √5
       = (((1 + √5) / 2) - ((1 - √5)) / 2) / √5
       = ((1 + √5 - 1 + √5) / 2) / √5
       = (2√5 / 2) / √5
       = √5 / √5
       = 1

さて、n≧2 の場合、次のように表現することが可能。

Fib(n) = (φ^n - ψ^n) / √5
       = (φ^(n-2)・φ^2 - ψ^(n-2)・ψ^2) / √5
       = (φ^(n-2)・(φ + 1) - ψ^(n-2)・(ψ + 1)) / √5
       = (φ^(n-1) + φ^(n-2) - ψ^(n-1) - ψ^(n-2)) / √5
       = (φ^(n-1) - ψ^(n-1)) / √5 + (φ^(n-2) - ψ^(n-2)) / √5
       = Fib(n-1) + Fib(n-2)

よって、「ヒント」の命題は示せた。

あってる？


Q.E.D.

－