問題1.13

Fib(n)が φ^n /√5 に最も近い整数であることを、帰納法を用いて証明せよ。
φ = (1 + √5)/2 ≒ 1.61803398874989
φ^2 = φ + 1

いわゆる黄金比のこと。

証明なんて何年ぶりだろう...、自力で解くのは正直無理でしたm(__)m。
AnswerBookを写経しながら、自分の言葉に書き換えながら理解していきました。

[仮定]
φ = (1 + √5) / 2

Fib(n) = if (n == 0) 0
         elsif (n == 1) 1
         else Fib(n - 1) + Fib(n - 2)

[結論]
Fib(n) - 0.5 < φ^n /√5 < Fib(n) + 0.5

[証明]
ψ = (1 - √5) / 2 とすると、
Fib(n) = (φ^n - ψ^n) / √5

∵
f(n) = (φ^n - ψ^n) / √5 とする

n = 0 の時
Fib(0) = 0
f(0) = (1 - 1) / √5  = 0

n = 1 の時
Fib(1) = 1
f(1) = (φ - ψ) / √5
     = (1 + √5) - (1 - √5) / 2*√5 
     = 2√5 / 2√5
     = 1

n > 1 の時
Fib(n) = f(n)
Fib(n + 1) = f(n + 1)

とすると

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

  φ^n * φ + φ^n を、φ^nでくくりだす。(ψも同様)
= (φ + 1)φ^n

           = (φ + 1)φ^n - (ψ + 1)ψ^n / √5
          
φ + 1 , ψ + 1 は変換できる。

φ + 1 = (1 + √5) / 2 + 1 = (3 + √5) / 2 = (6 + 2√5) / 4 = φ^2
ψ + 1 = (1 - √5) / 2 + 1 = (3 - √5) / 2 = (6 - 2√5) / 4 = ψ^2

           = (φ^(n + 2) - ψ^(n + 2)) / √5
           = f(n + 2)

従って、 
Fib(n + 2) = f(n + 2)

上記の結果を利用して、結論を証明する。

g(n) = φ^n / √5 とすると、
h(n) = ψ^n / √5 とすると、

Fib(n) = g(n) - h(n)
g(n) = Fib(n) + h(n)
Fib(n) - |h(n)| < g(n) < Fib(n) + |h(n)|


    

    
ψ
    
 < 0.62
    
n > 1 であれば、

    

    
ψ^n
    
 < 
    
ψ
    
 < 0.62
    
√5 < 2.23606889564336 なので

    

    
ψ^n /√5
    
 < 0.5
    
また　n = 0 の場合は、

    

    
ψ^0 /√5
    
 = 
    
1 /√5
    
 = 0.447213411871319..
    
0.44.. < 0.5 なので成立

∴
Fib(n) - 0.5 < φ^n /√5 < Fib(n) + 0.5

証明終了