Fibonacci数列的通项公式

 

很经典的问题，尽力讲的每个人都能懂，不需要专业知识。

题目：f(1)=f(2)=1, f(n+2)=f(n+1)+f(n), f(n)=?

首先让我们先不要管那个初始条件，只看差分方程。

它没有常数项，因此两边同乘以一个常数仍然是成立的。

f(n+3)=f(n+2)+f(n+1)

kf(n+2)=kf(n+1)+kf(n)

如果我们假设每一项一一对应的话，f(n)就是一个等比数列，设为c*k^n。

代入差分方程，提取公因子，得到k^2=k+1，这个一元二次方程有两个根，k1=(1+sqrt(5))/2, k2=(1-sqrt(5))/2。

不过考虑到初始条件，貌似两个根都不对...

别急，再仔细看看差分方程。

显而易见如果f(n)和g(n)满足，那么它们的线性组合a*f(n)+b*g(n)也是满足的！

假设f(n)=c1*k1^n+c2*k2^n，代入1和2处的值，就可以得到这么个方程组

（如果你懒得算那个平方，也可以改为代入0和1处的值，f(0)=0）

c1*k1+c2*k2=1

c1*k1^2+c2*k2^2=1

二元二次方程组是有唯一解的，就是c1=1/sqrt(5), c2=-1/sqrt(5)。

组装一下就可以得到最终的公式了，可以随便代入几个值看看对不对。

是不是很简单？