問題1.13

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

と仮定する。

f(0) = 0        ― (1)
f(1) = 1        ― (2)

となり、

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

となる。ここで、

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

であるので、それぞれ(3)に代入すると、

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

Fib(n)の定義は

         0                              n = 0
Fib(n) = 1                              n = 1
         Fib(n - 1) + Fib(n - 2)        otherwise.

であるから、(1)、(2)、(4)より

Fib(n) = f(n)   ― (5)

Fib(n)がφ^n / √5に最も近い整数であるなら、

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

が成り立つ。(5)より、

               f(n) - 0.5 < φ^n / √5 < f(n) + 0.5
   (φ^n - ψ^n) / √5 - 0.5 < φ^n / √5 < (φ^n - ψ^n) / √5 + 0.5
φ^n / √5 - ψ^n / √5 - 0.5 < φ^n / √5 < φ^n / √5 - ψ^n / √5 + 0.5      ― (7)

となる。ここで、

ψ^n / √5 = ((1 - √5) / 2)^n / √5

だが、

2 < √5 < 3

であるため、

|ψ^n / √5| < 0.5

は自明であり、(7)および(6)が成り立つ。よって、Fib(n)はφ^n / √5に最も近い整数である。

（証明終）