特征方程教程

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

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

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

找规律

首先我们来看一个漂亮的例子:$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\}$
这个数列也满足递推式!

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

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

另一个真相

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

不信么?$\{g_n\}=\{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\}$满足条件。
……

现在我们得到了强化的结论:如果等比数列$\{ f_n\},\{ g_n\}$分别满足递推式,那么$\{\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$

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

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

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

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

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

因此,这里的$\{a_n\},\{b_n\}\cdots$,其实和向量的基底比较类似——如果$\{a_n\},\{b_n\}\cdots$是“线性无关”的,那么我们就可以通过$\{a_n\},\{b_n\}\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{equation} \left\{ \begin{aligned} \alpha + \beta = 3 \\ 2\alpha + 3\beta = 8 \end{aligned} \right. \end{equation}$

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

特征方程

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

毛主席教导我们:自己动手,丰衣足食。我们要自己构造出一组解!

如何构造这一组解?通过刚刚的讨论,我们认为构造等比数列比较靠谱。那么我们不妨令以$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*a_n$的特征方程是:$x^2=x+2$
$a_{n+3}=5*a_{n+2}+3*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}}[(\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}$.

显然,$\displaystyle \lim_{n \to +\infty} f(n)=\frac{2}{3}$,此题选B。


CC0协议 @ ruanxingzhi 2017. CC0是啥玩意?
Home apps close