Chat (Lingr.com)
Informaiton
Daily
Column
- MySQL日本語の旅(5/1)
- アクセス向上秘伝(5/9)
- 一風変ったHaskellλ門(6/13)
- SICP Answer Book (5/31) 問題3.26追加
Zope Solution
Extra
アーカイブ
OSS案内所
Site Info
関連リンク
##(link2sicp "book-Z-H-11.html#%_thm_1.13" "Exercise 1.13")
解答例
[仮定]
φ = (1 + sqrt(5)) / 2
Fib(n) = if (n == 0)
then 0
else if (n == 1)
then 1
else Fib(n - 1) + Fib(n - 2)
[結論]
Fib(n) - 0.5 < φ^n / sqrt(5) < Fib(n) + 0.5
[証明]
ψ = (1 - sqrt(5)) / 2 とすると
Fib(n) = (φ^n - ψ^n) / sqrt(5)
∵ n = 0 のとき Fib(0) = 0 = (φ^0 - ψ^0) / sqrt(5)
n = 1 のとき Fib(1) = 1 = (φ^1 - ψ^1) / sqrt(5)
ここで、
n = k のとき Fib(k) = (φ^k - ψ^k) / sqrt(5)
n = k+1 のとき Fib(k+1) = (φ^(k+1) - ψ^(k+1)) / sqrt(5)
とすると
n = k+2 のとき
Fib (k+2) = Fib(k+1) + Fib(k)
= (φ^k - ψ^k) / sqrt(5) + (φ^(k+1) - ψ^(k+1)) / sqrt(5)
= ((φ^k - ψ^k) + (φ^(k+1) - ψ^(k+1))) / sqrt(5)
= ((φ+1)φ^k - (ψ+1)ψ^k) / sqrt(5)
= (φ^(k+2) - ψ^(k+2)) / sqrt(5)
∵ φ+1 = (3 + sqrt(5)) / 2 = (6 + 2 * sqrt(5)) / 4 = φ^2
ψ+1 = (3 - sqrt(5)) / 2 = (6 - 2 * sqrt(5)) / 4 = ψ^2
∴ n ≧ 0 なる任意の整数nについて、Fib(n) = (φ^n - ψ^n) / sqrt(5)
∴ Fib(n) - |ψ^n / sqrt(5)| < φ^n / sqrt(5) < Fib(n) + |ψ^n / sqrt(5)|
ここで |ψ| < 0.62 であるから
n < 1 のとき |ψ^n| < |ψ| < 0.62 であり、
|ψ^n / sqrt(5)| < 0.5 である。
∴ Fib(n) - 0.5 < φ^n / sqrt(5) < Fib(n) + 0.5
Q.E.D.
コード
##(sicp-answer-code "ex-1.13.scm")
