斐波那契数列计算

练习1.13 证明 $Fib(n)$ 是最接近 $\phi ^ n / \sqrt {5}$ 的整数，其中 $\phi = (1 + \sqrt {5}) / 2$。提示：利用归纳法和斐波那契数列的定义，证明 $Fib(n) = (\phi ^ n - \gamma ^ n) / \sqrt {5}$。

斐波那契数列定义如下：

$$ Fib(n) = \begin{cases} 0 & 如果n=0 \\ 1 & 如果n=1 \\ Fib(n-1)+Fib(n-2) & 否则 \end{cases} $$

这是SICP里的一个小练习。一种证明方法如下：

$$ \begin{aligned} & 若a_n为斐波那契数列，则a_{n+2}=a_{n+1}+a_{n}，a_1=1,a_2=1，n \in N_+。\\ & 设 \lambda \in R，则a_{n+2}+ \lambda a_{n+1} = (1+ \lambda) a_{n+1} + a_{n} \\ & 即 \frac {a_{n+2}+ \lambda a_{n+1}} {a_{n+1} + \frac {1} {1+ \lambda} a_{n}} = 1 + \lambda \\ & 令 \lambda = \frac {1} {1+ \lambda}，解得\lambda_1=\frac {-1-\sqrt {5}} {2}，\lambda_2=\frac {-1+\sqrt {5}} {2} \\ & 此时a_{n+1}+ \lambda a_n为等比数列，即 \\ & a_{n+1}+ \lambda_1 a_n = (1+\lambda_1)(1+\lambda_1)^{n-1} = (1+\lambda_1)^n \quad (1) \\ & a_{n+1}+ \lambda_2 a_n = (1+\lambda_2)(1+\lambda_2)^{n-1} = (1+\lambda_2)^n \quad (2) \\ & (2)-(1)，得 \sqrt5 a_n = (\frac {1+\sqrt5} 2) ^ n - (\frac {1-\sqrt5} 2) ^ n \\ & 所以 a_n = \frac {(\frac {1+\sqrt5} 2) ^ n - (\frac {1-\sqrt5} 2) ^ n } {\sqrt5} \\ & n=0时可得a_0=0，符合定义。所以a_n即为斐波那契数列的通项公式。\\ & 因为-1 < \frac {1-\sqrt5} 2 < 0，所以当n越来越大时，(\frac {1-\sqrt5} 2) ^ n会趋近于0，且正负符号交替出现。\\ & 因此可以说Fib(n)是最接近 \phi ^ n / \sqrt {5} 的整数。 \end{aligned} $$