形式陈述

阶数为 $k$$k$ 的线性递推可写为

$$ a_n=c_1(n)a_{n-1}+\cdots+c_k(n)a_{n-k}+g(n), \qquad n\ge k, $$$$a_n=c_1(n)a_{n-1}+\cdots +c_k(n)a_{n-k}+g(n),n\ge k,$$

其中系数和序列值位于给定交换含幺环中。若 $g(n)=0$$g(n)=0$，称齐次；若 $c_i(n)$$c_i(n)$ 与 $n$$n$ 无关，称常系数。给定 $a_0,\ldots,a_{k-1}$$a_0,\dots ,a_{k-1}$ 后，显式递推唯一决定后续项。

常系数齐次递推

$$ a_n=c_1a_{n-1}+\cdots+c_ka_{n-k} $$$$a_n=c_1{a}_{n-1}+\cdots +c_k{a}_{n-k}$$

对应特征多项式

$$ r^k-c_1r^{k-1}-\cdots-c_k. $$$$r^k-c_1{r}^{k-1}-\cdots -c_k.$$

直觉

线性递推把下一项写成前几项的线性反馈。在域或适当扩域上的常系数情形可分解为指数模式，重根会额外产生多项式因子。

例子与边界

Fibonacci 数满足 $F_n=F_{n-1}+F_{n-2}$$F_n=F_{n-1}+F_{n-2}$，特征根为 $\frac{1\pm\sqrt5}{2}$$\frac{1\pm \sqrt{5}}{2}$。递推“阶数 $k$$k$”通常还隐含最高滞后项实际出现；若 $c_k=0$$c_k=0$，可降低有效阶数。特征根方法需在包含足够根的域中解释，非齐次或变系数情形需要其他方法。

推论与应用

线性递推可用矩阵幂、特征多项式或生成函数求解，并描述动态规划、自动机计数和离散线性系统。对常系数递推，其 OGF 通常为有理函数；反向也可由有理 OGF 得到最终线性递推。

参考资料

• Ronald L. Graham, Donald E. Knuth, and Oren Patashnik, Concrete Mathematics, 2nd ed., Addison-Wesley, 1994，Ch. 6。
• Richard P. Stanley, Enumerative Combinatorics, Vol. 1, 2nd ed., Cambridge University Press, 2011，§4.1。