常系数齐次线性递推式浅析

定义

常系数线性递推式：形如 $a_n=c_1{a}_{n-1}+c_2{a}_{n-2}+\cdots +c_k{a}_{n-k}+g(n)$ 的递推式。$c_i(1\le i\le k)$ 为常系数。称这个递推式为 $k$ 阶的。

常系数齐次线性递推式：$g(n)=0$ 的常系数线性递推式。

特征方程

需要使用特征方程来求解常系数齐次线性递推式的通项公式。

假设通项公式具有 $a_n=r^n$ 的形式，带入递推式中可得：

$$r^n=c_1{r}^{n-1}+c_2{r}^{n-2}+\cdots +c_k{r}^{n-k}$$

移项：

$$\begin{array}{rl}{r}^n-c_1{r}^{n-1}-c_2{r}^{n-2}-\cdots -c_k{r}^{n-k}& =0\\ r^{n-k}(r^k-c_1{r}^{k-1}-c_2{r}^{k-2}-\cdots -c_k)& =0\end{array}$$

显然，若要让 $r^{n-k}\not\equiv 0$，则：

$$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$$

通过初始条件即可求得通项公式。