Untitled

定义

对于序列 $(a_n) = (a_0, a_1\cdots)$ 满足线性递归关系 $a_n = c_1 a_{n-1} + c_2 + a_{n-2} + \cdots + c_k a_{n-k}$，其中 $c_1, c_2, \cdots, c_k$ 是常数。
例如，我们常见的斐波那契数列 $F_n = F_{n-1} + F_{n-2}$ 就是一个线性递归关系。

二阶线性递归关系

定义：$a_n = c_1 a_{n-1} + c_2 a_{n-2}$，其中 $c_1, c_2$ 是常数且 $c_2\not = 0$。

特征多项式 characteristic polynomial

$\mathcal{X}(t) = t^2 - c_1 t - c_2$ ，写成解的形式，就是 $\mathcal{X}(t) = (t - r_1)(t - r_2)$，其中 $r_1, r_2$ 是 $\mathcal{X}(t)$ 的根。

通项定理 (两个实数根)

在 $r_1\not = r_2$ 的情况下，通项公式为 $a_n = \alpha r_1^n + \beta r_2^n$，其中 $\alpha, \beta$ 是常数，可以通过初始条件解出。

初始条件

$a_0 = \alpha + \beta$，$a_1 = \alpha r_1 + \beta r_2$。

证明

令 $A(x) = \sum_{n = 0}^\infty a_n x^n$, 我们将前两项提出来，得到

$A(x) = a_0 + a_1 x + \sum_{n = 2}^\infty a_n x^n = a_0 + a_1 x + \sum_{n = 2}^\infty (c_1 a_{n-1} + c_2 a_{n-2})x^n$

然后给 $a_{n-1}$ 和 $a_{n-2}$ 乘上 $x$ 与 $x^2$，得到 $A(x) = a_0 + a_1 x + c_1 x\sum_{n = 2}^\infty ( a_{n-1} x^{n-1}) + c_2 x^2 \sum_{n = 2}^\infty (a_{n-2} x^{n-2})$，然后将 $a_{n-1}$ 和 $a_{n-2}$ 用 $A(x)$ 代替，得到 $A(x) = a_0 + a_1 x + c_1 x A(x) + c_2 x^2 A(x) - a_0c_1x$，
整理得到 $A(x) = \frac{a_0 + a_1 x - a_0 c_1 x}{1 - c_1 x - c_2 x^2}$ ，然后将 $A(x)$ 展开成分式，得到 $A(x) = \frac{\alpha}{1 - r_1 x} + \frac{\beta}{1 - r_2 x}$，然后展开成幂级数，得到 $A(x) = \sum_{n = 0}^\infty (\alpha r_1^n + \beta r_2^n)x^n$，所以 $a_n = \alpha r_1^n + \beta r_2^n$。

通项定理 (两个相同根)

如果特征方程有两个相同的根 $r_1 = r_2 = r$，则通项公式为 $a_n = (\alpha + \beta n)r^n$，其中 $\alpha, \beta$ 是常数，可以通过初始条件解出。

证明

和前面写过的证明类似，我们得到 $A(x) = \frac{a_0 + (a_1 - a_1 c_0) x}{(1-rx)^2}$，然后将 $A(x)$ 展开成分式，得到 $A(x) = \frac{\alpha}{1 - r x} + \frac{\beta}{(1 - r x)^2}$，然后展开成幂级数，得到 $A(x) = \sum_{n = 0}^\infty (\alpha + \beta n)r^n x^n$，所以 $a_n = (\alpha + \beta n)r^n$