线性递推入门

递推关系是描述数列或算法复杂度的基本语言。一个数列 $\{a_n\}$ 如果满足

a_n = c_1 a_{n-1} + c_2 a_{n-2} + \cdots + c_k a_{n-k} + f(n),

就称为 $k$ 阶常系数线性递推。当 $f(n) \equiv 0$ 时称为齐次，否则称为非齐次。本文聚焦如何系统求解这类递推。

Definition

一个 $k$ 阶常系数线性递推形如

a_n + c_1 a_{n-1} + c_2 a_{n-2} + \cdots + c_k a_{n-k} = f(n),

其中 $c_i$ 为常数， $f(n)$ 为驱动项。若 $f(n) \equiv 0$ ，则称为齐次递推。

齐次线性递推：特征方程法

对于齐次递推

a_n = c_1 a_{n-1} + c_2 a_{n-2} + \cdots + c_k a_{n-k},

假设解具有指数形式 $a_n = r^n$ ，代入后得到其特征方程

r^k - c_1 r^{k-1} - c_2 r^{k-2} - \cdots - c_k = 0.

特征根互异

若特征方程有 $k$ 个不同根 $r_1, r_2, \dots, r_k$ ，则通解为

a_n = A_1 r_1^n + A_2 r_2^n + \cdots + A_k r_k^n,

其中系数 $A_i$ 由初始条件确定。

重根情况

若 $r$ 是 $m$ 重根，则它在通解中贡献

(A_0 + A_1 n + \cdots + A_{m-1} n^{m-1}) r^n.

直观上，重根会引入多项式因子来保持解空间的维数。

例子：Fibonacci 数列

Fibonacci 数列满足

F_n = F_{n-1} + F_{n-2}, \quad F_0 = 0,\ F_1 = 1.

特征方程为 $r^2 - r - 1 = 0$ ，根为

r_{1,2} = \frac{1 \pm \sqrt{5}}{2}.

因此

F_n = A \left(\frac{1+\sqrt{5}}{2}\right)^n + B \left(\frac{1-\sqrt{5}}{2}\right)^n.

代入 $F_0 = 0$ 、 $F_1 = 1$ 可解得 $A = 1/\sqrt{5}$ 、 $B = -1/\sqrt{5}$ ，即 Binet 公式

F_n = \frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt{5}}{2}\right)^n - \left(\frac{1-\sqrt{5}}{2}\right)^n\right].

非齐次线性递推

非齐次递推的通解结构为

a_n = a_n^{(h)} + a_n^{(p)},

其中 $a_n^{(h)}$ 是对应齐次递推的通解， $a_n^{(p)}$ 是一个特解。

Theorem

非齐次线性递推的任意两个解之差都是对应齐次递推的解。因此通解等于齐次通解加上任意一个特解。

寻找特解时，通常根据 $f(n)$ 的形式猜测：

$f(n)$ 的形式	特解猜测形式
常数 $C$	常数 $A$ （若 1 不是特征根）
$n$ 的多项式	同次多项式
$C \cdot \alpha^n$	$A \cdot \alpha^n$ （若 $\alpha$ 不是特征根）
$C \cdot \alpha^n$ 且 $\alpha$ 是 $m$ 重特征根	$A n^m \alpha^n$

例子：汉诺塔

汉诺塔移动次数满足

T_n = 2T_{n-1} + 1, \quad T_1 = 1.

对应齐次递推 $T_n^{(h)} = 2T_{n-1}^{(h)}$ 的通解为 $T_n^{(h)} = A \cdot 2^n$ 。由于驱动项是常数 $1$ ，且 $1$ 不是特征根 $2$ ，设特解为常数 $B$ 。代入得

B = 2B + 1 \implies B = -1.

于是 $T_n = A \cdot 2^n - 1$ 。由 $T_1 = 1$ 得 $A = 1$ ，故

T_n = 2^n - 1.

生成函数视角

生成函数是处理递推的另一种强大工具。对数列 $\{a_n\}$ 定义普通生成函数

G(x) = \sum_{n=0}^{\infty} a_n x^n.

将递推关系两边乘以 $x^n$ 并求和，可以把递推转化为关于 $G(x)$ 的代数方程。解出 $G(x)$ 后再展开即可得到 $a_n$ 的显式公式。

例子：Fibonacci 的生成函数

由 $F_n = F_{n-1} + F_{n-2}$ 及 $F_0=0, F_1=1$ ，可得

G(x) = x + x G(x) + x^2 G(x),

即

G(x) = \frac{x}{1 - x - x^2}.

对分母因式分解并部分分式展开后，同样能得到 Binet 公式。

常见误区与技巧

Warning

在猜测非齐次特解时，如果猜测形式已经是齐次解的一部分，需要乘以 $n$ 的适当幂次，否则无法得到有效的特解。

初始条件要足够： $k$ 阶递推需要 $k$ 个连续初始值才能唯一确定解。
复数根的处理：若特征根为复数，通常用欧拉公式化为三角函数形式，这在物理和信号处理中尤为常见。
变系数递推：本文方法仅适用于常系数情形；变系数递推通常需要其他技巧，如生成函数、特殊函数或近似方法。

总结

常系数线性递推的求解可归纳为三步：

写出特征方程并求根，得到齐次通解。
根据驱动项形式猜测非齐次特解，必要时乘以 $n$ 的幂次。
利用初始条件确定通解中的待定系数。

生成函数则提供了一种统一且机械的视角，尤其适合处理复杂边界条件或组合计数问题。掌握这两种方法，就能应对大多数算法分析和离散数学中的递推问题。