SICP問題1.13

すっかり忘れ去った証明問題。

φ=(1 + √5)/2 の時、 Fib(n)が (φ^n)/(√5)に最も近い整数であることを証明せよ
ヒント：ψ=(1 - √5)/2とする。帰納法とFibonnacci数の定義を用い
Fib(n)=((φ^n) - (ψ^n))/√5を証明せよ

ということで以下の感じ。

Fibonacchi 数の定義は
n = 0 の場合 Fib(0) = 0
n = 1 の場合 Fib(1) = 1
n > 1 の場合 Fib(n) = Fib(n - 1) + Fib(n - 2)

n=0 の時
φ^0 = 1
ψ^0 = 1
右辺 = (1 - 1)/√5 = 0
左辺 = Fib(0) = 0
∴左辺 = 右辺 … (1)

n=1 の時
φ^1 = (1 + √5)/2
ψ^1 = (1 - √5)/2
右辺 = (((1 + √5)/2) - ((1 - √5)/2))/√5
     = ((1 + √5 - 1 + √5)/2)/√5
     = (2√5/2)/√5
     = 1
左辺 = Fib(1) = 1
∴左辺 = 右辺 … (2)

n=k, n=k+1 の時、両方で左辺 = 右辺が成り立つと仮定する…(3)
Fib(k) = ((φ^k) - (ψ^k))/√5
Fib(k+1) = ((φ^k+1) - (ψ^k+1))/√5

n=k+2の時
Fib(k+2) = Fib(k + 2 - 1) + Fib(k + 2 - 2)
         = Fib(k + 1) + Fib(k)
         = ((φ^(k+1)) - (ψ^(k+1)))/√5 + ((φ^k) - (ψ^k))/√5
         = ((φ^(k+1)) - (ψ^(k+1)) + (φ^k) - (ψ^k))/√5
         = (φ^k)(1 + φ) - (ψ^k)(1 + ψ) … (4)
ここで
φ = (1 + √5)/2
ψ = (1 - √5)/2
のため
1 + φ = 1 + (1 + √5)/2
       = (3 + √5)/2
       = (6 + 2√5)/4
φ^2 = ((1 + √5)/2)^2
     = ((1^2) + (2*1*√5) + (√5^2))/(2^2)
     = (1 + 2√5 + 5)/4
     = (6 + 2√5)/4
よって
1 + φ= φ^2
同様に
1 - ψ = 1 + (1 - √5)/2
       = (3 - √5)/2
       = (6 - 2√5)/4
ψ^2 = ((1 - √5)/2)^2
     = ((1^2) - (2*1*√5) + (√5^2))/(2^2)
     = (1 - 2√5 + 5)/4
     = (6 - 2√5)/4
1 + ψ= ψ^2
となる。
ここから(4)の式は
         = (φ^k)(1 + φ) - (ψ^k)(1 + ψ)
         = (φ^k)(φ^2) - (ψ^k)((ψ^2)
         = φ^(k + 2) - ψ^(k + 2)
となり、(n >= 2)の任意の n について
Fib(n) = ((φ^n) - (ψ^n))/√5
が成り立つ。

よって
Fib(n) - ((ψ^n)/√5) < (φ^n)/√5 < Fib(n) + ((ψ^n)/√5)

ここで |ψ| = |(1 - √5)/2| = |(1 - 2.236...)/2| = |-0.6108| < 0.62 であるから
n < 1 のとき |(ψ^n)| < |ψ| < 0.62 であり、
|(ψ^n / √5)| < 0.5 である。

よって
Fib(n) - 0.5 < φ^n / √5 < Fib(n) + 0.5
が証明された