非齐次线性递推与高阶递推入口

常数项或随下标变化的项，可以先通过特解与累加处理。高阶递推的核心仍是“给足初值，验证递推”，不需要把数列问题全部转为高等代数。

一阶非齐次递推的有限公式

若 $a_{n+1}=pa_n+q_n$ ，反复代入得

a_n=p^{n-1}a_1+\sum_{k=1}^{n-1}p^{n-1-k}q_k\qquad(n\ge2).

该式可直接归纳证明。 $p=0$ 时宜直接用 $a_{n+1}=q_n$ ；避免在书写幂时引入不必要的 $0^0$ 争议。

例如 $a_1=0,a_{n+1}=2a_n+1$ ，得到 $a_n=2^{n-1}-1$ 。若系数也随下标变化，则每个常数幂应改成相应的一段系数乘积，空乘积约定为 $1$ 。

特解加齐次解

求 $a_{n+1}=2a_n+n$ 、 $a_1=0$ 。尝试一次特解 $u_n=An+B$ ，代入比较系数得 $A=-1,B=-1$ ，即 $u_n=-n-1$ 。

令 $b_n=a_n-u_n=a_n+n+1$ ，则 $b_{n+1}=2b_n,b_1=2$ ，所以 $a_n=2^n-n-1$ 。复核初值和原递推即完成。

若右侧含 $2^n$ ，恰与齐次解同型，常数倍 $C2^n$ 无法产生所需差；此时尝试 $Cn2^n$ 。例如 $a_{n+1}-2a_n=2^n$ 的特解为 $n2^{n-1}$ 。

常系数高阶递推与互异特征根

一般地，形如 $a_{n+k}=F(n,a_n,\ldots,a_{n+k-1})$ 的关系称为 $k$ 阶递推式。给定前 $k$ 项且以后每一步函数值都有定义，才能依次确定整个数列。下面进一步要求 $F$ 对数列项为线性且系数不随下标变化。

设 $k\ge1$ ，数列满足

a_{n+k}=c_1a_{n+k-1}+\cdots+c_ka_n\quad(n\ge1),

其中 $c_i$ 是常数，给定前 $k$ 项后数列唯一确定。代入试探解 $a_n=r^{n-1}$ ，得到特征方程

r^k-c_1r^{k-1}-\cdots-c_k=0.

若该方程有 $k$ 个互异非零根 $r_1,\ldots,r_k$ ，则

a_n=\sum_{j=1}^k A_jr_j^{n-1},

其中 $A_j$ 由前 $k$ 项唯一确定。

证明。 每个 $r_j^{n-1}$ 满足递推，线性组合也满足。初值方程的系数矩阵为 $(r_j^{i-1})_{1\le i,j\le k}$ ，其行列式为 $\prod_{i<j}(r_j-r_i)\ne0$ 。这个范德蒙德行列式公式可由以下事实推出：行列式是各根的多项式，两个根相等时两列相同，故含每个差因子；两边总次数相同，再比较 $r_2r_3^2\cdots r_k^{k-1}$ 的系数均为1。因此初值方程唯一可解，所得数列由递推唯一性就是原数列。

二阶重根情形在二阶线性递推中完整证明。三阶重根及零根的完整处理见下一节；一般更高阶情形也应验证递推与全部初值。复根不自动产生周期；随 $n$ 变化的系数不适用常系数特征方程。

三阶递推中的重根与零根

设 $a_{n+3}=pa_{n+2}+qa_{n+1}+sa_n$ （ $n\ge0$ ），给定 $a_0,a_1,a_2$ ，特征多项式为 $P(t)=t^3-pt^2-qt-s$ 。当根都非零时，通项按重数分类：

特征根	通项
三个互异根 $r_1,r_2,r_3$	$a_n=A r_1^n+B r_2^n+C r_3^n$
二重根 $r$ 与单根 $t\ne r$	$a_n=(A+Bn)r^n+Ct^n$
三重根 $r$	$a_n=(A+Bn+Cn^2)r^n$

常数均由三个初值唯一确定。根与系数可在复数中处理；实数列出现非实根时，最终组合还须满足实初值。

为什么重根产生下标多项式

记移位运算 $E$ 把数列 $u_n$ 变为 $u_{n+1}$ 。递推等价于 $P(E)a=0$ 。各常系数差分因子可交换，因为它们都是 $E$ 的多项式。若 $u_n=r^nf(n)$ ，则

(E-r)u_n=r^{n+1}\bigl(f(n+1)-f(n)\bigr).

一次差分降低非零多项式的次数，所以 $r^n,nr^n,n^2r^n$ 分别被 $E-r,(E-r)^2,(E-r)^3$ 消去。这说明表中的每个候选项都满足相应递推。

还要说明三个初值总能确定系数。对二重根情形，若某个候选组合的前三项全零，由递推唯一性它以后也全零。将恒等于零的组合除以 $r^n$ 得 $A+Bn+C(t/r)^n=0$ 。连作两次差分，得到 $C(t/r)^n(t/r-1)^2=0$ ，所以 $C=0$ ，再得 $A=B=0$ 。因此三组初值向量线性无关，三元一次方程组对任意三个初值都有唯一解。三重根情形除以 $r^n$ 后是二次多项式，由它在 $n=0,1,2$ 的值唯一确定；互异根情形已由范德蒙德行列式证明。

零根怎样处理

含零根时，不能直接把 $n0^n$ 等写进通式来拟合所有初值。若

P(t)=t^jQ(t),\qquad Q(0)\ne0,

则 $P(E)a=0$ 等价于尾数列 $b_n=a_{n+j}$ 满足 $Q(E)b=0$ 。先对这条低阶尾数列使用非零根公式，再保留原来前 $j$ 项。若 $P(t)=t^3$ ，原递推就是 $a_{n+3}=0$ ：前三项任意，以后全零。

这个处理同样适用于常系数高阶递推中的零根。非齐次递推须先减去一个特解，随下标变化的系数则不能直接套常系数公式。

三阶例子与唯一性

考虑 $a_{n+3}=6a_{n+2}-11a_{n+1}+6a_n$ ， $n\ge0$ ，初值为 $a_0=3,a_1=6,a_2=14$ 。特征多项式为

r^3-6r^2+11r-6=(r-1)(r-2)(r-3).

因此三个候选数列 $1,2^n,3^n$ 分别满足递推；其和满足给定三个初值，故 $a_n=1+2^n+3^n$ 。

为什么验证足够：原递推可由前三项唯一算出第四项，再依次决定以后各项；两个满足相同递推与相同三个初值的数列必逐项相同。