前言：

建议在阅读前先看这篇：生成函数的简单应用

也可搭配视频食用：线性常系数齐次递推关系

在本文中，我们将介绍一种名为特征多项式的东西，利用它可以快捷方便的求解通项公式。

定义：

$$a_n + c_1a_{n-1} + ... c_ka_{n-k} = 0$$

$$a_0 = d_0, a_1 = d_1, ..., a_{k-1} = d_{k-1}$$

若$c_1,c_2,...,c_k;  d_0,d_1,...,d_{k-1}$都是常数，则上式称为$k$阶的线性常系数齐次递推关系。

我们定义上式的特征多项式为：$$C(x) = x^k + c_1x^{k-1} + ... + c_k$$

接下来，我们将通过一系列的推导来说明母函数与特征多项式的关系。

推导：

设序列$a$的母函数为：$$G(x) = a_0 + a_1x + a_2x^2 + ...$$

显然有：

$$x^k(a_k + c_1a_{k-1} + ... + c_ka_0) = 0$$

$$x^{k+1}(a_{k+1} + c_1a_{k} + ... + c_ka_1) = 0$$

接下来的$x^{k+2}, x^{k+3}, ...$也是同理。我们将等式两边分别相加，可以得到：

$$G(x) - \sum_{h=0}^{k-1}a_hx^h + c_1x[G(x) - \sum_{h=0}^{k-2}a_hx^h] + ... + c_kx^kG(x) = 0$$

移项后得：

$$(1 + c_1x + c_2x^2 + ... + c_kx^k)G(x) = \sum_{h=0}^{k-1} [c_hx^h(\sum_{j=0}^{k-1-h}a_jx^j)]$$

令：

$$P(x) = \sum_{h=0}^{k-1} [c_hx^h(\sum_{j=0}^{k-1-h}a_jx^j)]$$

$$R(x) = 1 + c_1x + c_2x^2 + ... + c_kx^k$$

则：

$$G(x) = \frac{P(x)}{R(x)}$$

然后我们考虑分母$R(x)$与特征多项式$C(x)$的关系：

$$R(x) = x^k[\frac{1}{x^k} + c_1\frac{1}{x^{k-1}} + ... + c_{k-1}\frac{1}{x} + c_k] = x^kC(\frac{1}{x})$$

因为$C(x) = 0$有$k$个根。

令：

$$C(x) = (x - a_1)^{k_1}(x - a_2)^{k_2}...(x-a_t)^{x_t}$$

$$k_1 + k_2 + ... + k_t = k$$

所以：

$$G(x) = \frac{P(x)}{(1-a_1x)^{k_1}(1-a_2x)^{k_2}...(1-a_tx)^{k_t}}$$

接下来，我们将分三类讨论（无重根，有重根，复数根），从而利用上面的式子求出通项公式。

无重根：

若特征多项式$C(x) = x^k + c_1x^{k-1} + ... + c_k$无重根。

则$G(x)$可化简为：

$$G(x) = \frac{l_1}{1-a_1x} + \frac{l_2}{1-a_2x} + ... + \frac{l_k}{1-a_kx} = \sum_{i=1}^{k} \frac{l_i}{1-a_ix}$$

于是我们得到：

$$a_n = \sum_{i=1}^{k} l_i * a_i^n$$

好像很有道理，可是我们不知道$l_i$的值啊？

这很好办，我们已经知道了$a_0, a_1, ..., a_{k-1}$的值，于是我们可以列出$k$个方程，从而解出$l_1 - l_k$的值。

做个例题试试：

　　写出特征多项式：$C(x) = x^2 - x - 12 = 0, (x-4)(x+3) = 0$

　　于是：$G(x) = \frac{P(x)}{(1-4x)(1 + 3x)}$

　　即：$G(x) = \frac{l_1}{1-4x} + \frac{l_2}{1+3x}$

　　得到：$a_n = l_14^n + l_2(-3)^n$

　　代入$a_0 = 3, a_1 = 26$，解得：$l_1 = 5, l_2 = -2$

　　所以：$a_n = 5 * 4^n - 2 * (-3)^n$

是不是比普通的母函数法方便多了。

 有重根：

设$\beta$是$C(x)$的$k$重根

则$G(x)$可化简为：

$$G(x) = \sum_{i=1}^{k} \frac{l_i}{(1- \beta x)^i}$$

于是：

$$a_n = \sum_{i=1}^{k} l_i C_{n+i-1}^{i-1} \beta^n$$

和无重根的情况一样，我们同样可以列出$k$个方程来求解$l_i$的值。

下面来看一个例题：

　　写出特征多项式：$C(x) = x^2 - 4x + 4 = 0, (x-2)^2 = 0$

　　于是$G(x) = \frac{l_1}{1 - 2x} + \frac{l_2}{(1 - 2x)^2}$

　　于是：$a_n = l_1 * 2^n + l_2(n+1)2^n$

　　代入：$a_0 = 1, a_1 = 4$，解得：$l_1 = 0, l_2 = 1$

　　所以：$a_n = (n+1)2^n$

复数根：

对于复数还不是太懂，先咕着。。。