【失踪人口回归】斐波那契数列通项的推导

~~我最近在认真的读书~~

对于递推式 $F_n=F_{n-1}+F_{n-2}$ （略去显然的边界情况

我们有生成函数 $G(z)=sum_{ngeq0}F_nz^n$

通过一个变形得到

$zG(z)=sum_{ngeq0}F_nz^{n+1}$

再变

$z^2G(z)=sum_{ngeq0}F_nz^{n+2}$

三式相减

$(1-z-z^2)G(z)=(F_1-F_0)z=z$

那么 $G(z)=frac{z}{1-z-z^2}$

到此我们有一个简洁的结果。对于生成函数的基本应用手段，我们应该将其展开成简单的幂级数形式。

幸运的是我们有

$frac{A}{1-az}=Asum_{ngeq0}(az)^n$

如果有两个类似的形式，就有可能凑出我们想要的 $G(z)$

问题现在变得非常简单

$frac{A}{1-az}+frac{B}{1-bz}=G(z)$

$frac{A(1-bz)+B(1-az)}{(1-az)(1-bz)}=frac{z}{1-z-z^2}$

幸于多项式恒等定理的正确性，稍有数学基础的人都能很快的想出a,b的解法

那么我们有 $a=frac{1+sqrt5}{2},b=-frac{1-sqrt5}{2}$

同样的，我们得到 $A=-B=frac{1}{sqrt5}$

回到幂级数展开

$frac{A}{1-az}+frac{B}{1-bz}\=Asum_{ngeq0}(az)^n+Bsum_{ngeq0}(bz)^n\=sum_{ngeq0}(Aa^n+Bb^n)z^n\=sum_{ngeq0}A(a^n-b^n)z^n$

此时其实结果已经得到，就是 $F_n=A(a-b)^n=frac{1}{sqrt5}(frac{sqrt5+1}{2}^n+frac{sqrt5-1}{2}^n)$