一、常系数线性齐次递推方程

1. 定义

$$\{\begin{array}{rl}& H(n)-a_1(n-1)-a_{2}H(n-2)-...-a_{k}H(n-k)=0\\ & H(0)=b_0\\ & H(1)=b_1\\ & H(2)=b_2\\ & ...\\ & H(k-1)=b_{k-1}\end{array}$$

这是关于$H(n)$的递推方程，其中：$n\ge k,a_k\ne 0$

2. 特征方程

递推方程的特征方程为
$$x^k-a_1{x}^{k-1}-...-a_{k-1}x-a_k=0$$

特征方程的根为递推方程的特征根。

3. 递推方程的通解

若$q_1,q_2,...,q_k$是递推方程不等的特征根，则$c_1{q}_1^n+c_2{q}_2^n+...+c_k{q}_k^n$是该递推方程的通解，其中$c_1,c_2,...,c_k$是任意常数。

若$q$是递推方程的$i$重特征根，则$(c_1+c_{2}n+...+c_k{n}^{i-1})q^n$是该递推方程的通解，其中$c_1,c_2,...,c_k$是任意常数。

将初始条件代入通解中，即可解得$c_1,c_2,...,c_k$，求出该递推方程的特解。

4. 例题

【例 1】求解递推方程
$$\{\begin{array}{rl}& H(n)=H(n-1)+H(n-2)\\ & H(0)=1\\ & H(1)=1\end{array}$$
【解】特征方程为$x^2-x-1=0$，解得特征根为$x_1=\frac{1+\sqrt{5}}{2},x_2=\frac{1-\sqrt{5}}{2}$，得到递推方程的通解
$$H(n)=c_1{\left(\frac{1+\sqrt{5}}{2}\right)}^n+c_2{\left(\frac{1-\sqrt{5}}{2}\right)}^n$$
代入初值$H(0)=1,H(1)=1$得到方程组
$$\{\begin{array}{rl}& H(0)=c_1+c_2=1\\ & H(1)=c_1\left(\frac{1+\sqrt{5}}{2}\right)+c_2\left(\frac{1-\sqrt{5}}{2}\right)=1\end{array}$$
解得
$$\{\begin{array}{rl}& c_1=\frac{\left|\begin{array}{cc}1& 1\\ 1& \frac{1-\sqrt{5}}{2}\end{array}\right|}{\left|\begin{array}{cc}1& 1\\ \frac{1+\sqrt{5}}{2}& \frac{1-\sqrt{5}}{2}\end{array}\right|}=\frac{1}{\sqrt{5}}\frac{1+\sqrt{5}}{2}\\ & c_2=\frac{\left|\begin{array}{cc}1& 1\\ \frac{1+\sqrt{5}}{2}& 1\end{array}\right|}{\left|\begin{array}{cc}1& 1\\ \frac{1+\sqrt{5}}{2}& \frac{1-\sqrt{5}}{2}\end{array}\right|}=-\frac{1}{\sqrt{5}}\frac{1-\sqrt{5}}{2}\end{array}$$
所以递推方程的通解为
$$H(n)=\frac{1}{\sqrt{5}}{\left(\frac{1+\sqrt{5}}{2}\right)}^{n+1}-\frac{1}{\sqrt{5}}{\left(\frac{1-\sqrt{5}}{2}\right)}^{n+1}$$

【例 2】求解递推方程
$$\{\begin{array}{rl}& H(n)-3H(n-1)+4H(n-3)=0\\ & H(0)=1\\ & H(1)=0\\ & H(2)=0\end{array}$$
【解】特征方程为$x^3-3x^2+4=0$，解得特征根为$x_1=-1,x_2=x_3=2$，得到递推方程的通解
$$H(n)=(c_1+c_{2}n)\cdot 2^n+c_3\cdot (-1{)}^n$$
代入初值$H(0)=1,H(1)=0,H(2)=0$得到方程组
$$\{\begin{array}{rl}& H(0)=c_1+c_3=1\\ & H(1)=2(c_1+c_2)-c_3=2c_1+2c_2-c_3=0\\ & H(2)=4(c_1+2c_2)+c_3=4c_1+8c_2+c_3=0\end{array}$$
解得
$$\{\begin{array}{rl}& c_1=\frac{\left|\begin{array}{ccc}1& 0& 1\\ 0& 2& -1\\ 0& 8& 1\end{array}\right|}{\left|\begin{array}{ccc}1& 0& 1\\ 2& 2& -1\\ 4& 8& 1\end{array}\right|}=\frac{5}{9}\\ & c_2=\frac{\left|\begin{array}{ccc}1& 1& 1\\ 2& 0& -1\\ 4& 0& 1\end{array}\right|}{\left|\begin{array}{ccc}1& 0& 1\\ 2& 2& -1\\ 4& 8& 1\end{array}\right|}=-\frac{1}{3}\\ & c_3=\frac{\left|\begin{array}{ccc}1& 0& 1\\ 2& 2& 0\\ 4& 8& 0\end{array}\right|}{\left|\begin{array}{ccc}1& 0& 1\\ 2& 2& -1\\ 4& 8& 1\end{array}\right|}=\frac{4}{9}\end{array}$$
所以递推方程的通解为
$$H(n)=\left(\frac{5}{9}-\frac{1}{3}n\right)2^n+\frac{4}{9}(-1{)}^n$$

二、常系数线性非齐次递推方程

1. 定义

$$\{\begin{array}{rl}& H(n)-a_1(n-1)-a_{2}H(n-2)-...-a_{k}H(n-k)=f(n)\\ & H(0)=b_0\\ & H(1)=b_1\\ & H(2)=b_2\\ & ...\\ & H(k-1)=b_{k-1}\end{array}$$

这是关于$H(n)$的递推方程，其中：$n\ge k,a_k\ne 0,f(n)\ne 0$

2. 特征方程

递推方程的特征方程为
$$x^k-a_1{x}^{k-1}-...-a_{k-1}x-a_k=0$$

特征方程的根为递推方程的特征根。

3. 递推方程的通解

设$H_0(n)$是对应齐次方程的通解，$H^{\ast }(n)$是一个非齐次方程的特解，则该非齐次方程的通解为
$$H(n)=H_0(n)+H^{\ast }(n)$$

4. 确定非齐次方程的特解

$f(n)$	特解$H^{\ast }(n)$的形式
$a$（$1$不是特征根）	$A$
$a$（$1$是特征根）	$nA$
$an+b$ （$1$不是特征根）	$An+B$
$an+b$ （$1$是特征根）	$n(An+B)$
$a{n}^2+bn+c$（$1$不是特征根）	$A{n}^2+Bn+C$
$a{n}^2+bn+c$（$1$是特征根）	$n(A{n}^2+Bn+C)$
$a{\beta }^n$（$\beta$不是特征根）	$A{\beta }^n$
$a{\beta }^n$（$\beta$是$i$重特征根）	$A{n}^i{\beta }^n$
$(an+b){\beta }^n$（$\beta$不是特征根）	$(An+B){\beta }^n$
$(an+b){\beta }^n$（$\beta$是$i$重特征根）	$(An+B)n^i{\beta }^n$

5. 例题

【例 1】求解递推方程
$$\{\begin{array}{rl}& H(n)=H(n-1)+n-1\\ & H(1)=0\end{array}$$
【解】特征方程为$x^2-x=0$，解得特征根为$x_1=1,x_2=0$，得到对应齐次方程的通解
$$H_0(n)=c_1\cdot 1^n+c_2\cdot 0^n=c_1$$
由于特征根中有$1$，故设特解为
$$H^{\ast }(n)=n(An+B)=A{n}^2+Bn$$
代入递推方程得
$$(A{n}^2+Bn)-[A(n-1{)}^2+B(n-1)]=2An-A+B=n-1$$
对比等号两边系数，得$A=\frac{1}{2},B=-\frac{1}{2}$，所以递推方程的通解为
$$H(n)=H_0(n)+H^{\ast }(n)=c_1+\frac{1}{2}{n}^2-\frac{1}{2}n$$
代入初值条件$H(1)=0$，得$c_1=0$，最终得到
$$H(n)=\frac{1}{2}{n}^2-\frac{1}{2}n$$

【例 2】求解递推方程
$$\{\begin{array}{rl}& H(n)=2H(n-1)+1\\ & H(1)=1\end{array}$$
【解】特征方程为$x^2-2x=0$，解得特征根为$x_1=2,x_2=0$，得到对应齐次方程的通解
$$H_0(n)=c_1\cdot 2^n+c_2\cdot 0^n=c_1\cdot 2^n$$
设特解为$H^{\ast }(n)=A$，代入递推方程得$A=2A+1$，解得$A=-1$，所以递推方程的通解为
$$H(n)=H_0(n)+H^{\ast }(n)=c_1\cdot 2^n-1$$
代入初值条件$H(1)=1$，得$c_1=1$，最终得到
$$H(n)=2^n-1$$

【例 3】求解递推方程
$$\{\begin{array}{rl}& H(n)-4H(n-1)+4H(n-2)=2^n\\ & H(0)=1\\ & H(1)=5\end{array}$$
【解】特征方程为$x^2-4x+4=0$，解得特征根为$x_1=x_2=2$，得到对应齐次方程的通解
$$H_0(n)=(c_1+c_{2}n)\cdot 2^n$$
由于$2$为二重特征根，故设特解为
$$H^{\ast }(n)=n^{2}A\cdot 2^n$$
代入递推方程得
$$n^{2}A\cdot 2^n-4(n-1{)}^{2}A\cdot 2^{n-1}+4(n-2{)}^{2}A\cdot 2^{n-2}=2^n$$
解得$A=\frac{1}{2}$，所以递推方程的通解为
$$H(n)=H_0(n)+H^{\ast }(n)=(c_1+c_{2}n)\cdot 2^n+n^2\cdot 2^{n-1}$$
代入初值条件得
$$\{\begin{array}{rl}& H(0)=c_1=1\\ & H(1)=2(c_1+c_2)+1=5\end{array}$$
解得$c_1=1,c_2=1$，最终得到
$$H(n)=(1+n)\cdot 2^n+n^2\cdot 2^{n-1}$$

三、其他解法

以上方法只适用于常系数线性递推方程，对于变系数递推方程和特征根为虚数的情况，还可以使用以下方法求解。

1. 数学归纳法（用于证明）

当待证结论为一阶形式时，使用第一数学归纳法：
$$\{\begin{array}{rl}（1）& 验证n=1时，命题H(n)正确\\ （2）& 假设n=k(k\ge 2)时，命题H(n)正确\\ （3）& 证明n=k+1时，命题H(n)正确\end{array}$$
当待证结论为二阶形式时，使用第二数学归纳法：
$$\{\begin{array}{rl}（1）& 验证n=1和n=2时，命题H(n)均正确\\ （2）& 假设n<k(k\ge 3)时，命题H(n)正确\\ （3）& 证明n=k时，命题H(n)正确\end{array}$$

2. 迭代归纳法

【例 1】求解递推方程
$$\{\begin{array}{rl}& H(n)-nH(n-1)=n!\\ & H(0)=2\end{array}$$
【解】由迭代法得
$$\begin{array}{rl}H(n)& =n!+nH(n-1)\\ & =n!+n[(n-1)!+(n-1)H(n-2)]\\ & =n!+n(n-1)!+n(n-1)H(n-2)\\ & =2n!+n(n-1)H(n-2)\\ & =2n!+n(n-1)[(n-2)!+(n-2)H(n-3)]\\ & =3n!+n(n-1)(n-2)H(n-3)\\ & =...\\ & =n\cdot n!+n!\cdot H(0)\\ & =n\cdot n!+n!\cdot 2\\ & =(n+2)\cdot n!\end{array}$$
为确保结果的正确性，使用数学归纳法进行验证：

（1）当$n=0$时，$H(0)=(0+2)\cdot 0!=2$，说明命题$H(n)$正确；

（2）假设$n=k(k\ge 1)$时，命题$H(n)$正确；

（3）当$n=k+1$时，
$$\begin{array}{rl}H(k+1)& =(k+1)!+(k+1)H(k)\\ & =(k+1)[k!+H(k)]\\ & =(k+1)[k!+(k+2)\cdot k!]\\ & =(k+1)[1+(k+2)]k!\\ & =[(k+1)+2)](k+1)!\end{array}$$
说明结果正确。

【例 2】求解递推方程
$$\{\begin{array}{rl}& (n-1)H(n)-nH(n-1)=0\\ & H(1)=1\end{array}$$
【解】由迭代法得
$$\begin{array}{rl}H(n)& =\frac{n}{n-1}H(n-1)\\ & =\frac{n}{n-1}\frac{n-1}{n-2}H(n-2)\\ & =\frac{n}{n-1}\frac{n-1}{n-2}\frac{n-2}{n-3}H(n-3)\\ & =...\\ & =\frac{n}{n-1}\frac{n-1}{n-2}\frac{n-2}{n-3}\cdot \cdot \cdot \frac{2}{1}H(1)\\ & =\frac{n!}{(n-1)!}H(1)\\ & =n\cdot H(1)\\ & =n\end{array}$$
由数学归纳法验证可知结果正确。

【例 3】求解递推方程
$$\{\begin{array}{rl}& (n-1)H(n)-nH(n-1)=1\\ & H(1)=1\end{array}$$

【解】这是一个非齐次变系数递推方程，先解对应的齐次方程$(n-1)H(n)-nH(n-1)=0$，由迭代法解得$H(n)=n\cdot H(1)$，即$\frac{H(n)}{n}=H(1)$。现将原非齐次方程凑成$\frac{H(n)}{n}$的形式，等式两边同除$n(n-1)$可得
$$\frac{H(n)}{n}-\frac{H(n-1)}{n-1}=\frac{1}{n(n-1)}$$
令$T(n)=\frac{H(n)}{n}$，得到一个新的递推方程
$$\{\begin{array}{rl}& T(n)-T(n-1)=\frac{1}{n(n-1)}\\ & T(1)=1\end{array}$$
所以有
$$\begin{array}{rl}T(n)& =[T(n)-T(n-1)]+[T(n-1)-T(n-2)]+...+[T(2)-T(1)]+T(1)\\ & =\sum _{k=2}^n[T(k)-T(k-1)]+T(1)\\ & =1+\sum _{k=2}^n\frac{1}{k(k-1)}\\ & =1+(1-\frac{1}{2}+\frac{1}{2}-\frac{1}{3}+...-\frac{1}{n-1}+\frac{1}{n-1}-\frac{1}{n})\\ & =2-\frac{1}{n}\end{array}$$
即：$H(n)=2n-1$

【例 4】求解递推方程
$$\{\begin{array}{rl}& (n+2)H(n)-(n-1)H(n-1)=1\\ & H(1)=1\end{array}$$
【解】这是一个非齐次变系数递推方程，先解对应的齐次方程$(n+2)H(n)-(n-1)H(n-1)=0$，由迭代法得
$$\begin{array}{rl}H(n)& =\frac{n-1}{n+2}H(n-1)\\ & =\frac{n-1}{n+2}\frac{n-2}{n+1}H(n-2)\\ & =\frac{n-1}{n+2}\frac{n-2}{n+1}\frac{n-3}{n}H(n-3)\\ & =...\\ & =\frac{n-1}{n+2}\frac{n-2}{n+1}\frac{n-3}{n}\cdot \cdot \cdot \frac{1}{4}H(1)\\ & =\frac{(n-1)!}{\frac{(n+2)!}{6}}H(1)\\ & =6\frac{(n-1)!}{(n+2)!}H(1)\\ & =\frac{6}{n(n+1)(n+2)}H(1)\end{array}$$
即$n(n+1)(n+2)H(n)=6H(1)$，现将原非齐次方程凑成$n(n+1)(n+2)H(n)$的形式，等式两边同乘$n(n+1)$可得
$$n(n+1)(n+2)H(n)-(n-1)n(n+1)H(n-1)=n(n+1)$$
令$T(n)=n(n+1)(n+2)H(n)$，得到一个新的递推方程
$$\{\begin{array}{rl}& T(n)-T(n-1)=n(n+1)\\ & T(1)=6\end{array}$$
所以有
$$\begin{array}{rl}T(n)& =\sum _{k=2}^n[T(k)-T(k-1)]+T(1)\\ & =6+\sum _{k=2}^{n}k(k+1)\end{array}$$
即
$$H(n)=\frac{1}{n(n+1)(n+2)}[6+\sum _{k=2}^{n}k(k+1)]$$

【例 5】求解递推方程
$$\{\begin{array}{rl}& nH(n)-H(n-1)=1\\ & H(1)=1\end{array}$$
【解】这是一个非齐次变系数递推方程，先解对应的齐次方程$nH(n)-H(n-1)=0$，由迭代法得
$$\begin{array}{rl}H(n)& =\frac{1}{n}H(n-1)\\ & =\frac{1}{n}\frac{1}{n-1}H(n-2)\\ & =\frac{1}{n}\frac{1}{n-1}\frac{1}{n-2}H(n-3)\\ & =...\\ & =\frac{1}{n!}H(1)\end{array}$$
即$n!H(n)=H(1)$，现将原非齐次方程凑成$n!H(n)$的形式，等式两边同乘$(n-1)!$可得
$$n!H(n)-(n-1)!H(n-1)=(n-1)!$$
令$T(n)=n!H(n)$，得到一个新的递推方程
$$\{\begin{array}{rl}& T(n)-T(n-1)=(n-1)!\\ & T(1)=1\end{array}$$
所以有
$$\begin{array}{rl}T(n)& =\sum _{k=2}^n[T(k)-T(k-1)]+T(1)\\ & =1+\sum _{k=2}^n(k-1)!\end{array}$$
即
$$H(n)=\frac{1}{n!}+\frac{1!}{n!}+\frac{2!}{n!}+...+\frac{(n-1)!}{n!}$$

3. 差消法

有些高阶递推方程，需要先使用差消法将其转化为一阶递推方程再求解更方便。

【例 1】求解递推方程
$$\{\begin{array}{rl}& H(n)=(n-1)[H(n-1)+H(n-2)]\\ & H(1)=0\\ & H(2)=1\end{array}$$
【解】由于直接迭代该二阶递推方程比较繁琐，因此使用差消法得
$$\begin{array}{rl}H(n)-nH(n-1)& =-[H(n-1)-(n-1)H(n-2)]\\ & =(-1{)}^2\cdot [H(n-2)-(n-2)H(n-3)]\\ & =(-1{)}^3\cdot [H(n-3)-(n-3)H(n-4)]\\ & =...\\ & =(-1{)}^{n-2}\cdot [H(2)-2H(1)]\\ & =(-1{)}^{n-2}\\ & =(-1{)}^n\end{array}$$
此时二阶递推方程转化为一阶递推方程为
$$\{\begin{array}{rl}& H(n)-nH(n-1)=(-1{)}^n\\ & H(1)=0\end{array}$$
这是一个变系数的递推方程，使用迭代法得
$$\begin{array}{rl}H(n)& =nH(n-1)+(-1{)}^n\\ & =n[(n-1)H(n-2)+(-1{)}^{n-1}]+(-1{)}^n\\ & =n(n-1)H(n-2)+n(-1{)}^{n-1}+(-1{)}^n\\ & =n(n-1)[(n-2)H(n-3)+(-1{)}^{n-2}]+n(-1{)}^{n-1}+(-1{)}^n\\ & =n(n-1)(n-2)H(n-3)+n(n-1)(-1{)}^{n-2}+n(-1{)}^{n-1}+(-1{)}^n\\ & =n(n-1)(n-2)(n-3)H(n-4)+n(n-1)(n-2)(-1{)}^{n-3}+n(n-1)(-1{)}^{n-2}+n(-1{)}^{n-1}+(-1{)}^n\\ & =...\\ & =[n(n-1)\cdot \cdot \cdot 2]\cdot H(1)+[n(n-1)\cdot \cdot \cdot 3]\cdot (-1{)}^2+[n(n-1)\cdot \cdot \cdot 4]\cdot (-1{)}^3+...+n(-1{)}^{n-1}+(-1{)}^n\\ & =[n(n-1)\cdot \cdot \cdot 3]\cdot (-1{)}^2+[n(n-1)\cdot \cdot \cdot 4]\cdot (-1{)}^3+...+n(-1{)}^{n-1}+(-1{)}^n\end{array}$$

4. 一些技巧

【例 1】求解递推方程
$$\{\begin{array}{rl}& H(n)=(1-a)H(n-1)+aH(n-2)\\ & H(1)=1-a\\ & H(2)=1-a+a^2\end{array}(a\ne 1)$$
【解】该题可以使用公式法求解，其特征方程为$(q-1)(q-a)=0$。现在使用另一种方法来解决。原方程可变形为
$$\begin{array}{r}H(n)-H(n-1)=-a[H(n-1)-H(n-2)]\end{array}$$
令$T(n)=H(n)-H(n-1)(n\ge 2)$，则得到一个新的递推方程
$$\{\begin{array}{rl}& T(n)=-aT(n-1)\\ & T(2)=a^2\end{array}(a\ne 1,n\ge 3)$$
注意到$T(n)$是一个公比为$-a$的等比数列，所以通项公式为$T(n)=T(2)(-a{)}^{n-2}(n\ge 3)$，即
$$T(n)=H(n)-H(n-1)=a^2\cdot (-a{)}^{n-2}=(-a{)}^2\cdot (-a{)}^{n-2}=(-a{)}^n$$
所以有
$$\begin{array}{rl}H(n)& =\sum _{k=2}^n[H(k)-H(k-1)]+H(1)\\ & =1-a+\sum _{k=2}^n[(-a{)}^k]\\ & =1-a+a^2-a^3+...+(-a{)}^n\end{array}$$

【例 2】求解递推方程
$$\{\begin{array}{rl}& H(n)=H(n-1)-H(n-2)\\ & H(1)=1\\ & H(2)=0\end{array}$$
【解】由于特征方程为虚数根（也同时说明解可能具有周期性），所以难以使用公式求解。原方程可变形为
$$\begin{array}{rl}H(n)& =H(n-1)-H(n-2)\\ & =[H(n-2)-H(n-3)]-H(n-2)\\ & =-H(n-3)\end{array}$$
所以递推方程变为
$$\{\begin{array}{rl}& H(n)=-H(n-3)\\ & H(1)=1\\ & H(2)=0\\ & H(3)=-1\end{array}$$
显然，这是一个分为三段的周期数列，即
$$\{\begin{array}{rlrlrl}& H(1)=1,& & H(4)=-1,& & H(7)=1,...\\ & H(2)=0,& & H(5)=0,& & H(8)=0,...\\ & H(3)=-1,& & H(6)=1,& & H(9)=-1,...\end{array}$$
写成表达式为
$$H(n)=\{\begin{array}{ll}(-1{)}^{k+1},& n=3k-2\\ 0,& n=3k-1\\ (-1{)}^k,& n=3k\end{array}(k\ge 1)$$

参考资料：《离散数学第2版（屈婉玲）》《离散数学学习指导与习题解析第2版（屈婉玲）》