1. 问题的数学表述
考虑一个线性齐次递推方程：
\[a_n = c_1 a_{n-1} + c_2 a_{n-2} + \cdots + c_k a_{n-k}, \quad (n \geq k),\]它是一个 $k$ -阶线性递推方程，依赖于初始条件 $a_0, a_1, \ldots, a_{k-1}$。
目标是找到递推序列的通解。
2. 将递推方程转化为矩阵形式
为了利用线性代数的工具，可以将递推方程写成矩阵形式。引入一个状态向量：
\[\mathbf{v}_n = \begin{bmatrix} a_n \\ a_{n-1} \\ \vdots \\ a_{n-k+1} \end{bmatrix}.\]则递推关系可以写为矩阵形式：
\[\mathbf{v}_n = A \mathbf{v}_{n-1},\]其中 $A$ 是一个 $k \times k$ 的状态转移矩阵：
\[A = \begin{bmatrix} c_1 & c_2 & \cdots & c_{k-1} & c_k \\ 1 & 0 & \cdots & 0 & 0 \\ 0 & 1 & \cdots & 0 & 0 \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & \cdots & 1 & 0 \end{bmatrix}.\]初始向量 $\mathbf{v}_0$ 则由初始条件决定。
3. 矩阵幂和特征根理论
解递推关系的核心问题是求矩阵 $A^n$ 的形式。根据线性代数的理论：
特征值分解
- 如果矩阵 $A$ 可对角化，则存在一个非奇异矩阵 $P$ 和对角矩阵 $D$，使得： \(A = P D P^{-1}, \quad \text{其中 } D = \mathrm{diag}(\lambda_1, \lambda_2, \ldots, \lambda_k).\)
- $A^n$ 可以快速计算为： \(A^n = P D^n P^{-1}, \quad \text{且 } D^n = \mathrm{diag}(\lambda_1^n, \lambda_2^n, \ldots, \lambda_k^n).\)
结果解释
- 对于每个特征值 $\lambda_i$，其对应的特征向量 $\mathbf{v}_i$ 满足： \(A^n \mathbf{v}_i = \lambda_i^n \mathbf{v}_i.\)
- 因此，矩阵 $A^n$ 的作用可以分解为特征值（$\lambda_i^n$）和特征向量的线性组合。
4. 从矩阵形式回到递推方程解
利用初始条件向量 $\mathbf{v}_0$ 的线性组合，可以表示通解为：
\[\mathbf{v}_n = \sum_{i=1}^k c_i \lambda_i^n \mathbf{v}_i,\]这对应于递推方程解的形式：
\[a_n = A_1 \lambda_1^n + A_2 \lambda_2^n + \cdots + A_k \lambda_k^n,\]其中：
- $\lambda_i$ 是矩阵 $A$ 的特征值（也是递推方程特征方程的根），
- $A_i$ 是常数，由初始条件决定。
5. 特征根理论的正确性
为了验证这种形式的正确性，必须确认以下几点：
(1) 特征方程的正确性
- 对于递推方程 $a_n = c_1 a_{n-1} + c_2 a_{n-2} + \cdots + c_k a_{n-k}$，特征方程是： \(\lambda^k - c_1 \lambda^{k-1} - c_2 \lambda^{k-2} - \cdots - c_k = 0.\)
- 这是矩阵 $A$ 的特征多项式，因此其根即为递推关系的特征值。
(2) 解的结构封闭性
- 由于矩阵 $A^n$ 是有限维线性空间上的线性变换，其作用形式必然可由特征值与特征向量描述。
- 这保证了解的形式可以写成 $\lambda_i^n$ 的线性组合。
(3) 初始条件的确定性
- 初始条件 $a_0, a_1, \ldots, a_{k-1}$ 唯一确定了常数 $A_i$.
- 因此，特征根理论生成的解形式是递推方程的唯一通解。
6. 结论
特征根理论之所以能够求解递推方程，关键在于：
- 递推方程本质上是一个线性变换（矩阵形式）；
- 矩阵幂的计算与特征值分解直接相关；
- 特征值和特征向量提供了描述递推序列的基本模式，解可以表示为特征值的幂次线性组合。
这种方法的正确性严格基于线性代数的特征值分解和矩阵理论.