小池有话说

Exercise 1.13. Prove that Fib(n) is the closest integer to \( \frac{\phi^{n}}{\sqrt{5}} \) , where \( \phi = \frac{1+\sqrt{5}}{2} \) . Hint: Let \( \psi = \frac{1-\sqrt{5}}{2} \) . Use induction and the definition of the Fibonacci numbers (see section 1.2.2) to prove that \( Fib(n) = \frac{\phi^{n}-\psi^{n}}{\sqrt{5}} \) .

练习 1.13. 证明 Fib(n) 是与 \( \frac{\phi^{n}}{\sqrt{5}} \) 最接近的整数，其中 \( \phi = \frac{1+\sqrt{5}}{2} \) . 提示：令 \( \psi = \frac{1-\sqrt{5}}{2} \) . 使用斐波那契数列的定义证明 \( Fib(n) = \frac{\phi^{n}-\psi^{n}}{\sqrt{5}} \) .

证：

首先证明

$$Fib(n) = \frac{\phi^{n}-\psi^{n}}{\sqrt{5}} \tag{1}$$

设 (1)式成立

展开以下式子

$$Fib(n+1) = \frac{\phi^{n+1}-\psi^{n+1}}{\sqrt{5}} = \frac{1}{2} \cdot Fib(n) + \frac{\phi^{n} + \psi^{n}}{2}$$ $$Fib(n+2) = \frac{\phi^{n+2}-\psi^{n+2}}{\sqrt{5}} = \frac{3}{2} \cdot Fib(n) + \frac{\phi^{n} + \psi^{n}}{2}$$

可证

$$Fib(n+2) = Fib(n+1) + Fib(n)$$

又

$$Fib(0) = \frac{\phi^{0}-\psi^{0}}{\sqrt{5}} = 0$$ $$Fib(1) = \frac{\phi^{1}-\psi^{1}}{\sqrt{5}} = 1$$ $$Fib(2) = \frac{\phi^{2}-\psi^{2}}{\sqrt{5}} = 1$$

故

$$Fib(2) = Fib(1) + Fib(0)$$

由归纳法可知 (1) 式 成立.

于是 $Fib(n)$ 可以拆成两数之差的形式

$$Fib(n) = \frac{\phi^{n}-\psi^{n}}{\sqrt{5}} = \frac{\phi^{n}}{\sqrt{5}}-\frac{\psi^{n}}{\sqrt{5}}$$

而 \( \frac{1}{\sqrt{5}} < \frac{1}{2} \) ，于是：

$$|\psi| = |\frac{1-\sqrt{5}}{2}| < 1 \Leftrightarrow |1-\sqrt{5}| < 2 \Leftrightarrow (1-\sqrt{5})^2 < 4 \Leftrightarrow 1 < \sqrt{5}$$

故

$$|\frac{\psi^{n}}{\sqrt{5}}| < \frac{1}{\sqrt{5}} < \frac{1}{2}$$

即

$$|Fib(n) - \frac{\phi^{n}}{\sqrt{5}}| < \frac{1}{2}$$

故得证： $Fib(n)$ 是与 \( \frac{\phi^{n}}{\sqrt{5}} \) 最接近的整数