特征方程学习笔记

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

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

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

一阶线性递推式

设数列 \(\{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\) 的通项。

解：