想必斐波那契数列大家是十分熟悉的, 毕竟我们都知道它的递推公式
$f[0] = 0$
$f[1] = 1$
$f[i] = f[i - 1] + f[i - 2]~~~~~i >= 2$

但是本文将要解释斐波那契的通项公式。
先上结论:
$f_i = \frac{\phi^i - \hat{\phi}^i}{\sqrt{5}} = \lfloor \frac{\phi^{i}}{\sqrt{5}} + \frac{1}{2} \rfloor$

数学归纳法证明:

$f_0 = \frac{\phi^{0} - \hat{\phi}^{0}}{\sqrt{5}} = \frac{1 - 1}{\sqrt{5}} = 0$
$f_1 = \frac{\phi^{1} - \hat{\phi}^{1}}{\sqrt{5}} = \frac{(1 + \sqrt{5} - (1 - \sqrt{5})) * \frac{1}{2}}{\sqrt{5}} = 1$

若$f_{i - 1}$和$f_{i - 2}$成立,

$f_i = \frac{\phi^{i - 1} - \hat{\phi}^{i - 1}}{\sqrt{5}} + \frac{\phi^{i - 2} - \hat{\phi}^{i - 2}}{\sqrt{5}}$
提公因式,得
= $\frac{1}{\sqrt{5}}[\phi^{i - 2}(\phi + 1) - \hat{\phi}^{i - 2}(\hat{\phi} + 1)]$

因为$\phi$和$\hat{\phi}$是方程$x^2 = x + 1$的两根,
因此
原式 = $\frac{1}{\sqrt{5}}[\phi^{i - 2}\phi^2 + \hat{\phi}^{i - 2}\hat{\phi}^2] = \frac{\phi^i - \hat{\phi}^i}{\sqrt{5}}$

可以发现$|\hat{\phi}| < 1,$
$\frac{|\hat{\phi}^i|}{\sqrt{5}} < \frac{1}{\sqrt{5}} < \frac{1}{2}$

分类讨论:
1.若$\frac{|\hat{\phi}^i|}{\sqrt{5}} > 0$
斐波那契数列每一项必为整数,
因此$\frac{\phi^i - \hat{\phi}^i}{\sqrt{5}}$为整数, 且小数部分$< 0.5$
因此$\frac{\phi^i}{\sqrt{5}} + \frac{1}{2}$后不会进位,下取整后得到正确答案.

2.若$\frac{|\hat{\phi}^i|}{\sqrt{5}} < 0$
同理,可知
$\frac{\phi^i - \hat{\phi}^i}{\sqrt{5}}$小数部分$> 0.5$
因此$\frac{\phi^i}{\sqrt{5}} + \frac{1}{2}$后会进位,下取整后得到正确答案.

证毕.