首先证明 \(Fib(n) = \frac{\phi^{n}-\psi^{n}}{\sqrt{5}}\) .
设 \(Fib(n) = \frac{\phi^{n}-\psi^{n}}{\sqrt{5}}\)
则 \(Fib(n+1) = \frac{\phi^{n+1}-\psi^{n+1}}{\sqrt{5}} = \frac{\phi^{n} \cdot \phi - \psi^{n} \cdot \psi}{\sqrt{5}} = \frac{\phi^{n} \cdot \frac{1+\sqrt{5}}{2} - \psi^{n} \cdot \frac{1-\sqrt{5}}{2}}{\sqrt{5}} = \frac{1}{2} \cdot \left( \frac{\phi^{n} - \psi^{n}}{\sqrt{5}} + \frac{\sqrt{5} \cdot \left( \phi^{n} + \psi^{n} \right) }{\sqrt{5}} \right) = \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{\phi^{n} \cdot \phi^{2} - \psi^{n} \cdot \psi^{2}}{\sqrt{5}} = \frac{\phi^{n} \cdot (\frac{1+\sqrt{5}}{2})^{2} - \psi^{n} \cdot (\frac{1-\sqrt{5}}{2})^{2}}{\sqrt{5}} = \frac{1}{2} \cdot \left( \frac{3 \cdot (\phi^{n} - \psi^{n})}{\sqrt{5}} + \frac{\sqrt{5} \cdot (\phi^{n} + \psi^{n}) }{\sqrt{5}} \right) = \frac{3}{2} \cdot Fib(n) + \frac{\phi^{n} + \psi^{n}}{2}\)
可证 \(Fib(n+2) = Fib(n+1) + Fib(n)\) .
又
\(\frac{\phi^{0}-\psi^{0}}{\sqrt{5}} = 0 = Fib(0)\)
\(\frac{\phi^{1}-\psi^{1}}{\sqrt{5}} = 1 = Fib(1)\)
由此可知 \(Fib(n) = \frac{\phi^{n}-\psi^{n}}{\sqrt{5}}\) 成立.
于是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\)
故 \(|\frac{\psi^{n}}{\sqrt{5}}| < \frac{1}{2}\) .
即 \(|Fib(n) - \frac{\phi^{n}}{\sqrt{5}}| < \frac{1}{2}\) .
故得证：Fib(n) 是与 \(\frac{\phi^{n}}{\sqrt{5}}\) 最接近的整数