使用归纳法来证明 $Fib(n) = (\phi^n - \psi^n)/\sqrt 5$ ，其中 $\phi = \frac{1 + \sqrt{5}}{2}$ , $\psi = \frac{1-\sqrt{5}}{2}$ 。

当 n = 0 时，

$$Fib(0) = (\phi^0 - \psi^0)/\sqrt{5}= 0 $$ 公式成立。当 n = 1 时，

$$Fib(0) = (\phi^1 - \psi^1)/\sqrt{5}= 1 $$ 公式成立。我们假设 n = k 时，如下公式成立

$$Fib(k) = (\phi^k - \psi^k)/\sqrt{5} $$ 则可以知道：

$$Fib(k+1) = (\phi^{k+1} - \psi^{k+1})/\sqrt{5} Fib(k+2) = (\phi^{k+2} - \psi^{k+2})/\sqrt{5} $$ 我们只需要证出 $Fib(k+2)=Fib(k+1)+Fib(k)$ 那么我们的假设就成立。

证明过程如下：

$$ Fib(k)+Fib(k+1) & =\frac{\phi^k-\psi^k}{\sqrt{5}} + \frac{\phi^{k+1}-\psi^{k+1}}{\sqrt{5}} \\ & =\frac{1}{\sqrt{5}}(\phi^k-\psi^k+\frac{1+\sqrt{5}}{2}\phi^k-\frac{1-\sqrt{5}}{2}\psi^k) \\ & =\frac{1}{\sqrt{5}}(\frac{3+\sqrt{5}}{2}\phi^k-\frac{3-\sqrt{5}}{2}\psi^k) \\ & =\frac{1}{\sqrt{5}}(\phi^2\phi^k + \psi^2\psi^k) \\ & = Fib(k+2) \\ $$ 所以假设成立

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

$$\frac{\psi^n}{\sqrt{5}} < 1 $$ 所以 Fib(n) 是最接近 $\frac{\phi^n}{\sqrt{5}}$ 的整数。