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)。 组装一下就可以得到最终的公式了，可以随便代入几个值看看对不对。 是不是很简单？
Comments
Post a Comment