特征方程教程

我们常常会遇到一些递推式，例如著名的斐波那契数列：$F_{n+2}=F_n+F_{n+1}(F_1=1,F_2=1)$.在这种情况下，往往难以推出通项。

如果我们要编程求$F_n$，只需要矩阵快速幂就行了——可以在$O\left(\log n\right)$的时间复杂度内求出答案。有没有更“数学”的解法，来求出通项公式呢？

我们尝试用一种叫做“特征方程”的科技，来解决这类问题。实际上，这玩意很简单，个中原理也不复杂。（有公式恐惧症的不要跑呀，这篇文章没几个公式的）

找规律

首先我们来看一个漂亮的例子：$a_{n+2}=5\cdot a_{n+1}-6\cdot a_n$
真是让人摸不着头脑？那么现在给出一个已知条件：$f_n=2^{n-1}$这个数列满足上述递推式。

$\{1,2,4,8,16\cdots \}$，代入一看，果然。

有没有更一般的规律？我们来发掘一下……
$\{3\cdot f_n\}=\{3,6,12,24,48\cdots \}$
这个数列也满足递推式！

多找几个例子，我们注意到一个事实：若等比数列$\left\{f_n\right\}$满足递推式，那么$\{\lambda \cdot f_n\}$也满足递推式。

证明：把原递推式两边都乘上$\lambda$就行了，不碍事。

另一个真相

现在告诉您另一个事实：$g_n=3^{n-1}$这个等比数列，竟然也满足原递推式。

不信么？$\left\{g_n\right\}=\{1,3,9,27,81\cdots \}$
代入，发现真的也行！

根据我们刚刚的结论，$\{\lambda \cdot g_n\}$也是满足递推式的。能不能把$f$和$g$综合起来呢？

$\{3f_n+5g_n\}=\{8,21,57,159\cdots \}$满足条件。
$\{7f_n+2g_n\}=\{9,20,46,110\cdots \}$满足条件。
……

现在我们得到了强化的结论：如果等比数列$\left\{f_n\right\},\left\{g_n\right\}$分别满足递推式，那么$\{\alpha f_n+\beta g_n\}$也满足递推式。证明很简单。

形而上

形而上者谓之道，形而下者谓之器。上面的例子是特殊的，我们试图给出一些一般性的结论：

现有递推式$f_n+p_{k-1}{f}_{n-1}+p_{k-2}{f}_{n-2}+\cdots +p_0{f}_{n-k}=0$,称为$k$阶线性齐次递推方程。
这只是把原来的递推式换了个写法，例如斐波那契数列：$f_n-f_{n-1}-f_{n-2}=0$

我们刚刚发现：如果已知数列$\left\{a_n\right\},\left\{b_n\right\},\left\{c_n\right\}\cdots$都满足这个递推式，那么它们的“线性组合”$\{\alpha \cdot a_n+\beta \cdot b_n+\gamma \cdot c_n\cdots \}$也满足递推式。

将$\left\{a_n\right\},\left\{b_n\right\}\cdots$称作此递推方程的解。

依据这个结论，我们只需要知道一组解$\left\{a_n\right\},\left\{b_n\right\}\cdots$，我们就可以拼凑出各种各样的数列，满足递推关系。但是需要指出：

如果解$\left\{b_n\right\}$可以通过解$\left\{a_n\right\}$直接得到，那么$\left\{b_n\right\}$的存在就是无意义的了。
如果解$\left\{c_n\right\}$可以通过解$\left\{a_n\right\},\left\{b_n\right\}$直接得到，那么$\left\{c_n\right\}$的存在也没有意义了。

打个比方：对于二元一次方程组，如果我们知道$x+y=2$，那么$2x+2y=4$这个方程就是毫无用处的。

因此，这里的$\left\{a_n\right\},\left\{b_n\right\}\cdots$，其实和向量的基底比较类似——如果$\left\{a_n\right\},\left\{b_n\right\}\cdots$是“线性无关”的，那么我们就可以通过$\left\{a_n\right\},\left\{b_n\right\}\cdots$拼凑出每一个合法的数列。

实际操作

通过刚刚的讨论，我们发现一个基本事实：拿到一个递推式，如果我们能求出它的一组解，还知道$f_n$的前几项——我们就能推出数列的通项公式。

还是以$a_{n+2}=5\cdot a_{n+1}-6\cdot a_n$为例。我们找到了一组解： $f_n=2^{n-1},g_n=3^{n-1}$

根据之前的结论，可以令$a_n=\alpha 2^{n-1}+\beta 3^{n-1}$.

而我们现在又知道$f_1=3,f_2=8$。遂直接代入柿子：
$\{\begin{array}{c}\alpha +\beta =3\\ 2\alpha +3\beta =8\end{array}$

解出$\alpha =1,\beta =2$.也就是说，$a_n=2^{n-1}+2\cdot 3^{n-1}$. 而根据通项公式算出来的前几项是：$\{3,8,22,62\cdots \}$，检验一下，发现确实是吻合的。

特征方程

我们刚刚求出了通项公式，关键在于我们凭空得知了一个结论：$\left\{f_n\right\},\left\{g_n\right\}$满足递推式。然而天上并不会掉馅饼，我们以后拿到一个递推式，总不可能乞灵于一眼看出来一组解吧？

毛主席教导我们：自己动手，丰衣足食。我们要自己构造出一组解！

如何构造这一组解？通过刚刚的讨论，我们认为构造等比数列比较靠谱。那么我们不妨令以$q$为公比的等比数列满足$a_{n+2}=5\cdot a_{n+1}-6\cdot a_n$，那么柿子变成：
$q^2\cdot a_n=5q\cdot a_n-6\cdot a_n$
两边除以$a_n$：
$q^2=5q-6$，即$q^2-5q+6=0$，即$q=2$或$3$。

也就是说：凡是以$2$或$3$为公比的等比数列，都满足这个递推式。因此我们自己构造出了两组解：$f_n=2^{n-1},g_n=3^{n-1}$。

一般地：对于长得像上面递推式的柿子，以$x^p$代替$a_{n+p}$，得到的方程称作“特征方程”。

例如： $a_{n+2}=a_{n+1}+2\ast a_n$的特征方程是：$x^2=x+2$
$a_{n+3}=5\ast a_{n+2}+3\ast a_{n+1}+a_n$的特征方程是：$x^3=5x^2+3x+1$

解特征方程，得到的根就可以作为等比数列的公比。

习题

一、求斐波那契数列的通项公式：

$f_{n+2}=f_{n+1}+f_n$，特征方程为$x^2=x+1$.
解得：$x_1=\frac{1-\sqrt{5}}{2},x_2=\frac{1+\sqrt{5}}{2}$

不妨设$f_n=\alpha (x_1{)}^{n-1}+\beta (x_2{)}^{n-1}$.又已知$f_1=1,f_2=1$，代入则有：
$\alpha +\beta =1$
$\frac{1-\sqrt{5}}{2}\alpha +\frac{1+\sqrt{5}}{2}\beta =1$

解得：$\alpha =\frac{\sqrt{5}-1}{2\sqrt{5}},\beta =\frac{\sqrt{5}+1}{2\sqrt{5}}$

代入原柿子，即得：$f_n=\frac{\sqrt{5}-1}{2\sqrt{5}}(\frac{1-\sqrt{5}}{2}{)}^{n-1}+\frac{\sqrt{5}+1}{2\sqrt{5}}(\frac{1+\sqrt{5}}{2}{)}^{n-1}$

整理，得：$f_n=\frac{1}{\sqrt{5}}\left[\right(\frac{1+\sqrt{5}}{2}{)}^n-\frac{1-\sqrt{5}}{2}{)}^n]$.

二、NOIP2017提高组初赛，T10

若$f_0=0,f_1=1,f_{n+1}=\frac{f_n+f_{n-1}}{2}$,则随着$i$的增大，$f_i$将接近于（）。

A. $\frac{1}{2}$           B. $\frac{2}{3}$           C. $\frac{\sqrt{5}-1}{2}$           D. $1$

特征方程：$x^2=\frac{x+1}{2}$，解得$x_1=-\frac{1}{2},x_2=1$.
不妨设$f_n=\alpha \cdot (-\frac{1}{2}{)}^n+\beta$.

代入$f_0=0,f_1=1$，得：$\alpha =-\frac{2}{3},\beta =\frac{2}{3}$.
故：$f_n=-\frac{2}{3}\cdot (-\frac{1}{2}{)}^n+\frac{2}{3}$.

显然，$\underset{n\to +\infty }{lim}f\left(n\right)=\frac{2}{3}$，此题选B。