sicp 1.13
证明Fibonacci数列F(n)是最接近(a^n) / sqrt(5)的整数，其中a=(1+sqrt(5)) / 2。F(n) = 0, n = 0
1, n = 1
F(n-1) + F(n-2), n > 1
此递归式的特征方程为 C(t) = t^2 - t - 1 = 0，求解得t1 = (1+sqrt(5)) / 2，t2 = (1-sqrt(5)) / 2
设F(n) = k1t1^n + k2t2^n，代入初始条件，求解得k1 = 1/sqrt(5)，k2 = -1/sqrt(5)
则F(n) = (t1^n - t2^n) / sqrt(5)
|F(n) - (a^n) / sqrt(5)| = |t2^n/sqrt(5)| = |((sqrt(5) - 1) / 2)^n / sqrt(5)| < ((sqrt(5) - 1) / 2) / sqrt(5) = 0.276 < 0.5
又因为F(n)显然是整数，所以F(n)是最接近(a^n) / sqrt(5)的整数。
页:
[1]