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

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!} \]

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) \]