【前言】

如果要求斐波那契数列的第$10^{12}$项(不考虑数值的溢出),使用$f(n)=f(n-1)+f(n-2)$显然已经不够了,矩阵乘法优化是不错的选择。但如果要求第$10^{10^{12}}$项,矩阵乘法也已经无能为力。这时候就需要$f(n)$的通项公式:$f(n)=\frac{1}{\sqrt{5}}[(\frac{1+\sqrt{5}}{2})^{n}-(\frac{1-\sqrt{5}}{2})^{n}]$,结合快速幂求解了。

考场上不可能正好出斐波那契数列,就算出了也可能记不得通项式子。毛主席说,自己动手,丰衣足食。我们更应该学会自己推导通项公式。

【一】

先举个初中一定会学到的例子:求$f(n)=2^0+2^1+…+2^{n}$的通项公式。初中老师会说,$2f(n)=2^1+…+2^{n+1}$,则两式相减可得$f(n)=2^{n+1}-1$。

我们换一种思路:设$f(n)=pf(n-1)+q$,若有$t$满足$f(n)-t=p[f(n-1)-t]$,则有$f(n)=pf(n-1)+t-pt$,与所设的式子比较可得$q=t-pt$。对于我们给出的例子,显然前5项依次是:$1,3,7,15,31$,则有$f(n)=2f(n-1)+1$,所以,于是。可得$f(n)+1=2[f(n-1)+1]$。令$g(n)=f(n)+1$,则$g(n)=2g(n-1)$且$g(1)=2$,易得$g(n)=2^{n+1}$,故$f(n)=g(n)-1=2^{n+1}-1$。

【二】

在上一部分中,我们了解了$f(n)$可以用$f(n-1)$和常数表示时,通项公式的求法。但是很多问题里(例如斐波那契数列)$f(n)$必须用$f(n-1)$和$f(n-2)$表示(不能带常数)。我们先看一个比较简单的例子:$f(n)=5f(n-1)-6f(n-2)$。
不难看出,若$f(n)=2^{n}$,则显然满足条件。证明是显然的,把$2^{n}$带进去合并同类项然后约分即可。

我们还可以发现,$f(n)=2^{n+1}$也满足这个条件!同理,$f(n)=2^{n-1}$或者其他次方,只要是关于n的一次函数(系数为1)即可。观察到$2^n$是等比数列,也可以说$f(n)$满足条件时$\alpha f(n)$也满足($\alpha$为常数),证明也很简单,直接约掉就好。

实际上,$f(n)=3^{n}$也是满足条件的(但不要想当然地认为$f(n)=4^n$也满足)。

【三】

再来一个更强的结论:若等比数列$g(n)$和$h(n)$都满足$f(n)$的递推式,那么$\alpha g(n)+\beta h(n)$也满足($\alpha$和$\beta$为常数)。

这个式子的证明当然是显然的。

【四】

我们知道了$2^n$和$3^n$都满足原递推式$f(n)=5f(n-1)-6f(n-2)$,那么能不能通过给$2^n$和$3^n$配上合理的系数,凑出$f(n)$的通项公式呢?为了计算方便,我们给定$f(1)=8$,$f(2)=22$。

不妨令$f(n)=\alpha 2^n+\beta 3^n$,将$n=1$和$n=2$代入可以得到一个方程组,解得$\alpha =1$,$\beta =2$。算出前几项检验下,显然是正确的。

【五】

根据上面的推导我们知道,如果已知2个等比数列满足$f(n)$的递推式,我们就一定可以通过$f(n)$的两个特殊值列方程组,求出其通项公式。但是如何求出满足条件的等比数列呢?

不妨假设满足条件等比数列的公比为$ \lambda $,则有 ,约掉$f(n-2)$得。解方程,易得或$3$。

【六】

实际上,就是递推式$f(n)=5f(n-1)-6f(n-2)$的特征方程。

推广一下,递推式$f(n)=\alpha f(n-1)+\beta f(n-2)$的特征方程就是$\lambda ^2=\alpha \lambda +\beta$。换句话说,就是用1代替$f(n-2)$,代替$f(n-1)$,代替$f(n)$。解出来的就是满足递推式的等比数列,然后列方程即可。

再次推广,如果$f(n)$用$f(n-1)$到$f(n-x)$表示,那么用代替$f(n-x)$,代替$f(n-x+1)$……直到表示$f(n)$。

【七】

回到开头的问题:求斐波那契数列即$f(n)=f(n-1)+f(n-2)$的通项公式。

列出特征方程:

解得

又$f(1)=1$,$f(2)=1$

可得$\left\{\begin{matrix} \alpha + \beta =1 & & \ \frac{1-\sqrt5}{2}\alpha +\frac {1+\sqrt5}{2}\beta =1 & & \end{matrix}\right.$

解得

代入原式并整理,得$f(n)=\frac{1}{\sqrt{5}}[(\frac{1+\sqrt{5}}{2})^{n}-(\frac{1-\sqrt{5}}{2})^{n}]$。

最后更新: 2018年11月24日 07:36

原始链接: https://ruixiangjiang.github.io/2018/11/07/characteristic-equation/

× 请我吃糖~
打赏二维码