斐波那契递归公式如下
$$
F(0)=0\
F(1)=1\
F(n+2)=F(n+1)+F(n)
$$
通项公式是
$$
F(n)=(\phi^n-\gamma^n)/\sqrt5\
\phi=(1+\sqrt5)/2\
\gamma=(1-\sqrt5)/2
$$
下面利用递归公式和数学归纳法证明通项公式的正确性。
$$
F(0)=(\phi^0-\gamma^0)/\sqrt5=0\
F(1)=(\phi^1-\gamma^1)/\sqrt5=((1+\sqrt5)-(1-\sqrt5))/(2\sqrt5)=(2\sqrt5)/(2*\sqrt5)=1
$$
我们假设小于等于n都是成立的，下面需要证明n+1时公式也是成立的。
先证明一个和phi相关的等式
$$
\begin{split}
\phi^2&=((1+\sqrt5)/2)^2\
&=(1+5+2\sqrt5)/4\
&=(3+\sqrt5)/2\
&=(1+\sqrt5)/2+1\
&=\phi+1
\end{split}
\begin{split}
\gamma^2&=((1-\sqrt5)/2)^2\
&=(1+5-2\sqrt5)/4\
&=(3-\sqrt5)/2\
&=(1-\sqrt5)/2+1\
&=\gamma+1
\end{split}
$$
现在推导F(n+1)
$$
\begin{split}
F(n)+F(n-1)&=(\phi^n-\gamma^n)/\sqrt5+(\phi^{n-1}-\gamma^{n-1})/\sqrt5\
&=((\phi^n+\phi^{n-1})-(\gamma^n+\gamma^{n-1}))/\sqrt5\
&=((\phi^{n-1}(\phi+1)-\gamma^{n-1}(\gamma+1))/\sqrt5\
&=((\phi^{n-1}(\phi^2)-\gamma^{n-1}(\gamma^2))/\sqrt5\
&=(\phi^{n+1}-\gamma^{n+1})/\sqrt5\
&=F(n+1)
\end{split}
$$
其实，F(n)是距离(phi^n)/sqrt(5)最近的整数。
如何证明这一点呢？
F(n)和(phi^n)/sqrt(5)的距离是|(gamma^n)/sqrt(5)|，只要证明距离始终小于0.5即可。
gamma的绝对值是小于0.7的，n次方导致绝对值会越来越小，所以距离最远的时候也就是取n=0，gamma^0=1，除以sqrt(5)也是小于0.5的。