递推方程的几种解法

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

1. 定义

$$\left\{ \begin{aligned} &H(n)-a_1(n-1)-a_2H(n-2)-...-a_kH(n-k)=0 \\ &H(0)=b_0 \\ &H(1)=b_1 \\ &H(2)=b_2 \\ &... \\ &H(k-1)=b_{k-1} \end{aligned} \right.$$

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

2. 特征方程

递推方程的特征方程为

$$x^k-a_1x^{k-1}-...-a_{k-1}x-a_k=0$$

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

3. 递推方程的通解

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

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

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

4. 例题

【例 1】求解递推方程

$$\left\{ \begin{aligned} &H(n)=H(n-1)+H(n-2) \\ &H(0)=1 \\ &H(1)=1 \\ \end{aligned} \right.$$

【解】特征方程为$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$得到方程组

$$\left\{ \begin{aligned} &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{aligned} \right.$$

解得

$$\left\{ \begin{aligned} &c_1=\frac{\begin{vmatrix} 1 & 1 \\ 1 & \frac{1-\sqrt{5}}{2} \end{vmatrix}} {\begin{vmatrix} 1 & 1 \\ \frac{1+\sqrt{5}}{2} & \frac{1-\sqrt{5}}{2} \end{vmatrix}} = \frac{1}{\sqrt{5}} \frac{1+\sqrt{5}}{2}\\ &c_2=\frac{\begin{vmatrix} 1 & 1 \\ \frac{1+\sqrt{5}}{2} & 1 \end{vmatrix}} {\begin{vmatrix} 1 & 1 \\ \frac{1+\sqrt{5}}{2} & \frac{1-\sqrt{5}}{2} \end{vmatrix}} = -\frac{1}{\sqrt{5}} \frac{1-\sqrt{5}}{2}\\ \end{aligned} \right.$$

所以递推方程的通解为

$$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】求解递推方程

$$\left\{ \begin{aligned} &H(n)-3H(n-1)+4H(n-3)=0 \\ &H(0)=1 \\ &H(1)=0 \\ &H(2)=0 \end{aligned} \right.$$

【解】特征方程为$x^3-3x^2+4=0$，解得特征根为$x_1=-1,x_2=x_3=2$，得到递推方程的通解

$$H(n)=(c_1+c_2n)\cdot2^n+c_3\cdot(-1)^n$$

代入初值$H(0)=1,H(1)=0,H(2)=0$得到方程组

$$\left\{ \begin{aligned} &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{aligned} \right.$$

解得

$$\left\{ \begin{aligned} &c_1= \frac{\begin{vmatrix} 1 & 0 & 1 \\ 0 & 2 & -1 \\ 0 & 8 & 1 \end{vmatrix}} {\begin{vmatrix} 1 & 0 & 1 \\ 2 & 2 & -1 \\ 4 & 8 & 1\end{vmatrix}} = \frac{5}{9}\\ &c_2= \frac{\begin{vmatrix} 1 & 1 & 1 \\ 2 & 0 & -1 \\ 4 & 0 & 1 \end{vmatrix}} {\begin{vmatrix} 1 & 0 & 1 \\ 2 & 2 & -1 \\ 4 & 8 & 1\end{vmatrix}} = -\frac{1}{3}\\ &c_3= \frac{\begin{vmatrix} 1 & 0 & 1 \\ 2 & 2 & 0 \\ 4 & 8 & 0 \end{vmatrix}} {\begin{vmatrix} 1 & 0 & 1 \\ 2 & 2 & -1 \\ 4 & 8 & 1\end{vmatrix}} = \frac{4}{9} \end{aligned} \right.$$

所以递推方程的通解为

$$H(n)=\left(\frac{5}{9}-\frac{1}{3}n\right)2^n+\frac{4}{9}(-1)^n$$

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

1. 定义

$$\left\{ \begin{aligned} &H(n)-a_1(n-1)-a_2H(n-2)-...-a_kH(n-k)=f(n) \\ &H(0)=b_0 \\ &H(1)=b_1 \\ &H(2)=b_2 \\ &... \\ &H(k-1)=b_{k-1} \end{aligned} \right.$$

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

2. 特征方程

递推方程的特征方程为

$$x^k-a_1x^{k-1}-...-a_{k-1}x-a_k=0$$

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

3. 递推方程的通解

设$H_0(n)$是对应齐次方程的通解，$H^*(n)$是一个非齐次方程的特解，则该非齐次方程的通解为

$$H(n)=H_0(n)+H^*(n)$$

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

$f(n)$	特解$H^*(n)$的形式
$a$（$1$不是特征根）	$A$
$a$（$1$是特征根）	$nA$
$an+b$ （$1$不是特征根）	$An+B$
$an+b$ （$1$是特征根）	$n(An+B)$
$an^2+bn+c$（$1$不是特征根）	$An^2+Bn+C$
$an^2+bn+c$（$1$是特征根）	$n(An^2+Bn+C)$
$a\beta^n$（$\beta$不是特征根）	$A\beta^n$
$a\beta^n$（$\beta$是$i$重特征根）	$An^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】求解递推方程

$$\left\{ \begin{aligned} &H(n)=H(n-1)+n-1 \\ &H(1)=0 \end{aligned} \right.$$

【解】特征方程为$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^*(n)=n(An+B)=An^2+Bn$$

代入递推方程得

$$(An^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^*(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】求解递推方程

$$\left\{ \begin{aligned} &H(n)=2H(n-1)+1 \\ &H(1)=1 \end{aligned} \right.$$

【解】特征方程为$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^*(n)=A$，代入递推方程得$A=2A+1$，解得$A=-1$，所以递推方程的通解为

$$H(n)=H_0(n)+H^*(n)=c_1 \cdot 2^n-1$$

代入初值条件$H(1)=1$，得$c_1=1$，最终得到

$$H(n)=2^n-1$$

【例 3】求解递推方程

$$\left\{ \begin{aligned} &H(n)-4H(n-1)+4H(n-2)=2^n \\ &H(0)=1 \\ &H(1)=5 \end{aligned} \right.$$

【解】特征方程为$x^2-4x+4=0$，解得特征根为$x_1=x_2=2$，得到对应齐次方程的通解

$$H_0(n)=(c_1+c_2n) \cdot 2^n$$

由于$2$为二重特征根，故设特解为

$$H^*(n)=n^2A \cdot 2^n$$

代入递推方程得

$$n^2A \cdot 2^n-4(n-1)^2A \cdot 2^{n-1}+4(n-2)^2A \cdot 2^{n-2}=2^n$$

解得$A=\frac{1}{2}$，所以递推方程的通解为

$$H(n)=H_0(n)+H^*(n)=(c_1+c_2n) \cdot 2^n+n^2 \cdot 2^{n-1}$$

代入初值条件得

$$\left\{ \begin{aligned} &H(0)= c_1 = 1\\ &H(1)= 2(c_1+c_2)+1=5 \end{aligned} \right.$$

解得$c_1=1,c_2=1$，最终得到

$$H(n)=(1+n) \cdot 2^n+n^2 \cdot 2^{n-1}$$

三、其他解法

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

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

当待证结论为一阶形式时，使用第一数学归纳法：

$$\left\{ \begin{aligned} （1）&验证n=1时，命题H(n)正确\\ （2）&假设n=k(k \geq 2)时，命题H(n)正确\\ （3）&证明n=k+1时，命题H(n)正确 \end{aligned} \right.$$

当待证结论为二阶形式时，使用第二数学归纳法：

$$\left\{ \begin{aligned} （1）&验证n=1和n=2时，命题H(n)均正确\\ （2）&假设n<k(k \geq 3)时，命题H(n)正确\\ （3）&证明n=k时，命题H(n)正确 \end{aligned} \right.$$

2. 迭代归纳法

【例 1】求解递推方程

$$\left\{ \begin{aligned} &H(n)-nH(n-1)=n! \\ &H(0)=2 \end{aligned} \right.$$

【解】由迭代法得

$$\begin{aligned} 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{aligned}$$

为确保结果的正确性，使用数学归纳法进行验证：

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

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

（3）当$n=k+1$时，

$$\begin{aligned} 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{aligned}$$

说明结果正确。

【例 2】求解递推方程

$$\left\{ \begin{aligned} &(n-1)H(n)-nH(n-1)=0 \\ &H(1)=1 \end{aligned} \right.$$

【解】由迭代法得

$$\begin{aligned} 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}···\frac{2}{1}H(1) \\ &=\frac{n!}{(n-1)!}H(1) \\ &=n \cdot H(1) \\ &=n \end{aligned}$$

由数学归纳法验证可知结果正确。

【例 3】求解递推方程

$$\left\{ \begin{aligned} &(n-1)H(n)-nH(n-1)=1 \\ &H(1)=1 \end{aligned} \right.$$

【解】这是一个非齐次变系数递推方程，先解对应的齐次方程$(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}$，得到一个新的递推方程

$$\left\{ \begin{aligned} &T(n)-T(n-1)=\frac{1}{n(n-1)} \\ &T(1)=1 \end{aligned} \right.$$

所以有

$$\begin{aligned} 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{aligned}$$

即：$H(n)=2n-1$

【例 4】求解递推方程

$$\left\{ \begin{aligned} &(n+2)H(n)-(n-1)H(n-1)=1 \\ &H(1)=1 \end{aligned} \right.$$

【解】这是一个非齐次变系数递推方程，先解对应的齐次方程$(n+2)H(n)-(n-1)H(n-1)=0$，由迭代法得

$$\begin{aligned} 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}···\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{aligned}$$

即$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)$，得到一个新的递推方程

$$\left\{ \begin{aligned} &T(n)-T(n-1)=n(n+1) \\ &T(1)=6 \end{aligned} \right.$$

所以有

$$\begin{aligned} T(n)&=\sum_{k=2}^n[T(k)-T(k-1)]+T(1) \\ &=6+\sum_{k=2}^n k(k+1) \\ \end{aligned}$$

即

$$H(n)=\frac{1}{n(n+1)(n+2)}[6+\sum_{k=2}^n k(k+1)]$$

【例 5】求解递推方程

$$\left\{ \begin{aligned} &nH(n)-H(n-1)=1 \\ &H(1)=1 \end{aligned} \right.$$

【解】这是一个非齐次变系数递推方程，先解对应的齐次方程$nH(n)-H(n-1)=0$，由迭代法得

$$\begin{aligned} 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{aligned}$$

即$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)$，得到一个新的递推方程

$$\left\{ \begin{aligned} &T(n)-T(n-1)=(n-1)! \\ &T(1)=1 \end{aligned} \right.$$

所以有

$$\begin{aligned} T(n)&=\sum_{k=2}^n[T(k)-T(k-1)]+T(1) \\ &=1+\sum_{k=2}^n (k-1)! \\ \end{aligned}$$

即

$$H(n)=\frac{1}{n!}+\frac{1!}{n!}+\frac{2!}{n!}+...+\frac{(n-1)!}{n!}$$

【例 6】设$n$阶矩阵$A$和$B$，已知$AB=cB（c为常数）$，求证：$A^nB=c^nB$。

【证】使用迭代法：

$$\begin{aligned} A^nB &= A^{n-1} \cdot AB = A^{n-1} \cdot cB = c \cdot A^{n-1}B \\ &= cA^{n-2} \cdot AB = cA^{n-2} \cdot cB = c^2 \cdot A^{n-2}B \\ &=...\\ &= c^{n-1} \cdot AB = c^{n-1} \cdot cB\\ &= c^nB \end{aligned}$$

3. 差消法

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

【例 1】求解递推方程

$$\left\{ \begin{aligned} &H(n)=(n-1)[H(n-1)+H(n-2)] \\ &H(1)=0 \\ &H(2)=1 \end{aligned} \right.$$

【解】由于直接迭代该二阶递推方程比较繁琐，因此使用差消法得

$$\begin{aligned} 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{aligned}$$

此时二阶递推方程转化为一阶递推方程为

$$\left\{ \begin{aligned} &H(n)-nH(n-1)=(-1)^n \\ &H(1)=0 \end{aligned} \right.$$

这是一个变系数的递推方程，使用迭代法得

$$\begin{aligned} 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)···2] \cdot H(1)+[n(n-1)···3] \cdot (-1)^{2}+[n(n-1)···4] \cdot (-1)^{3}+...+n(-1)^{n-1}+(-1)^n \\ &=[n(n-1)···3] \cdot (-1)^{2}+[n(n-1)···4] \cdot (-1)^{3}+...+n(-1)^{n-1}+(-1)^n \\ \end{aligned}$$

4. 一些技巧

【例 1】求解递推方程

$$\left\{ \begin{aligned} &H(n)=(1-a)H(n-1)+aH(n-2) \\ &H(1)=1-a \\ &H(2)=1-a+a^2 \end{aligned} \right. (a \neq 1)$$

【解】该题可以使用公式法求解，其特征方程为$(q-1)(q-a)=0$。现在使用另一种方法来解决。原方程可变形为

$$\begin{aligned} H(n)-H(n-1)=-a[H(n-1)-H(n-2)] \end{aligned}$$

令$T(n)=H(n)-H(n-1)(n \geq 2)$，则得到一个新的递推方程

$$\left\{ \begin{aligned} &T(n)=-aT(n-1) \\ &T(2)=a^2 \end{aligned} \right. (a \neq 1,n \geq 3)$$

注意到$T(n)$是一个公比为$-a$的等比数列，所以通项公式为$T(n)=T(2)(-a)^{n-2}(n \geq 3)$，即

$$T(n)=H(n)-H(n-1)=a^2 \cdot (-a)^{n-2}=(-a)^2 \cdot (-a)^{n-2}=(-a)^n$$

所以有

$$\begin{aligned} 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{aligned}$$

【例 2】求解递推方程

$$\left\{ \begin{aligned} &H(n)=H(n-1)-H(n-2) \\ &H(1)=1 \\ &H(2)=0 \end{aligned} \right.$$

【解】原方程可变形为

$$\begin{aligned} H(n)&=H(n-1)-H(n-2) \\ &=[H(n-2)-H(n-3)]-H(n-2) \\ &=-H(n-3) \end{aligned}$$

【例 2】求解递推方程

$$\left\{ \begin{aligned} &H(n)=H(n-1)-H(n-2) \\ &H(1)=1 \\ &H(2)=0 \end{aligned} \right.$$

【解】由于特征方程为虚数根（也同时说明解可能具有周期性），所以难以使用公式求解。原方程可变形为

$$\begin{aligned} H(n)&=H(n-1)-H(n-2) \\ &=[H(n-2)-H(n-3)]-H(n-2) \\ &=-H(n-3) \end{aligned}$$

所以递推方程变为

$$\left\{ \begin{aligned} &H(n)=-H(n-3) \\ &H(1)=1 \\ &H(2)=0 \\ &H(3)=-1 \end{aligned} \right.$$

显然，这是一个分为三段的周期数列，即

$$\left\{ \begin{aligned} &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{aligned} \right.$$

写成表达式为

$$H(n)= \begin{cases} (-1)^{k+1},&n=3k-2 \\ 0,&n=3k-1 \\ (-1)^k,&n=3k \\ \end{cases} (k \geq 1)$$

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