特征方程 学习笔记

特征方程的原理貌似是线性代数的东西。

但是如果只是使用的话，不需要了解这么多。

特征方程可以用于快速求解一些递推式的通项

---

一阶线性递推式

设数列 $\{a_n\}$ 满足

$$a_1 = b \\ a_{n} = ca_{n-1} + d,~n>1$$

其中 $c \ne 0 \land c\ne 1$ ，求这个数列的通项公式。

定义 $x=cx+d$ 为原递推式的特征方程。

设上述特征方程的根为 $x_0$ ，则

• 当 $x_0 = a_1$ 时，$\{a_n\}$ 为常数列，即 $a_n=a_1$ 。

• 当 $x_0 \ne a_1$ 时，

  $$a_n = (a_1-x_0) \cdot c^{n-1} + x_0$$

---

例：

已知数列 $\{a_n\}$ 满足

$$a_1 = 4 \\ a_n = -\dfrac{1}{3} a_{n-1} - 2,~n>1$$

求 $a_n$ 的通项。

解：特征方程为 $x +\dfrac{1}{3}x + 2=0$ ，解得 $x_0 = -\dfrac{3}{2}$

因为 $x_0 \ne a_1$ ，所以原数列不是常数列，则根据公式

$$\begin{aligned} a_n &= (a_1 - x_0) \cdot c^{n-1} + x_0 \\ &= \left(4-\left(-\frac{3}{2}\right)\right) \times \left(-\dfrac{1}{3}\right)^{n-1} +\left(-\frac{3}{2}\right) \\&=\frac{11}{2} \times \left(-\frac{1}{3}\right)^{n-1} - \frac{3}{2} \end{aligned}$$

---

齐次递推式

设数列 $\{x_n\}$ 满足

$$a_kx_{n+k} + a_{k-1}x_{n+k-1} + \cdots + a_0x_n = 0$$

其特征方程为

$$a_k \lambda^k + a_{k-1} \lambda^{k-1} + \cdots + a_1\lambda + a_0 = 0$$

若得到不同的特征根 $\{\lambda _i\}$，则通解为

$$x_n = \sum c_i \lambda _i^{n-1}$$

注：如果下标是从 $x_0$ 开始的，那就是 $x_n = \sum c_i \lambda _i^{n}$

$c_i$ 的计算只需要代入 $x_1,x_2,\cdots,x_k$ 解方程即可。

若其中的特征根 $\lambda _i$ 的重数为 $s$ ，则将通解中相关的那 $s$ 项 $\lambda _i^{n-1}$ 换成下面这 $s$ 项的和

$$\lambda_i^{n-1} + n\lambda_i^{n-1} + \cdots + n^{s-1}\lambda_i^{n-1}$$

这么说有点抽象，我们来考虑 $k=2$ 的情况。

设数列 $\{a_n\}$ 满足

$$a_1=A,a_2=B \\a_n = pa_{n-1}+qa_{n-2} ,~n> 2$$

特征方程为

$$x^2-px-q=0$$

解这个方程可以得到两个解 $x_1,x_2$ ，若 $x_1 \ne x_2$ 则

$$a_n=c_1 x_1^{n-1} + c_2 x_2^{n-1}$$

将 $a_0=A,a_1=B$ 代入得

$$\begin{cases} c_1 + c_2 = A \\c_1 x_1+c_2 x_2=B \end{cases}$$

解出 $c_1,c_2$ 即可。

---

例1：已知数列 $\{a_n\}$ 满足

$$a_1 = 1,~a_2 = 1 \\ a_n = 3a_{n-1} + 4a_{n-2},~n>2$$

求 $a_n$ 的通项。

解：

特征方程为

$$x^2 -3x-4=0$$

解得

$$x_1 = 4,~x_2 = -1$$

根据 $a_n=c_1 x_1^{n-1} + c_2 x_2^{n-1}$ ，代入方程

$$\begin{cases} c_1 + c_2 = 1 \\c_1 \times 4+c_2 \times (-1)=1 \end{cases}$$

解得

$$c_1 = \frac{1}{5}, ~c_2 = \dfrac{4}{5}$$

则

$$a_n = \dfrac{1}{5} \times 4^{n-1} + \dfrac{4}{5} \times (-1)^{n-1}$$

---

例2：已知数列 $\{a_n\}$ 满足

$$a_1 = 1,~a_2 = 2 \\ a_n = 2a_{n-1} - a_{n-2},n>2$$

求 $a_n$ 的通项。

解：

其实这个题可以用等差中项做（

特征方程为

$$x^2-2x+1 = 0$$

解得 $x_1 = x_2 = 1$ ，则

$$a_n = c_1 x_1^{n-1} + nc_2x_2^{n-1} = c_1 + nc_2$$

代入方程

$$\begin{cases} c_1 + 1\times c_2 = 1 \\c_1 +2\times c_2=2 \end{cases}$$

解得

$$c_1 = 0, c_2 = 1$$

则

$$a_n = n$$

---

参考文献：

[1] https://wenku.baidu.com/view/a7ea0676a417866fb84a8ecf.html

[2] https://www.luogu.com.cn/blog/xgzc/solution-p5110

[3] https://www.zhihu.com/question/39086469/answer/79659010