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)|
n > 1 であれば、
√5 < 2.23606889564336 なので
また n = 0 の場合は、
| ψ^0 /√5 |
= |
1 /√5 |
= 0.447213411871319.. |
0.44.. < 0.5 なので成立
∴
Fib(n) - 0.5 < φ^n /√5 < Fib(n) + 0.5
証明終了
