文章目录
- 一、常系数线性齐次递推方程
-
- 1. 定义
- 2. 特征方程
- 3. 递推方程的通解
- 4. 例题
- 二、常系数线性非齐次递推方程
-
- 1. 定义
- 2. 特征方程
- 3. 递推方程的通解
- 4. 确定非齐次方程的特解
- 5. 例题
- 三、其他解法
-
- 1. 数学归纳法（用于证明）
- 2. 迭代归纳法
- 3. 差消法
- 4. 一些技巧
一、常系数线性齐次递推方程
1. 定义
{
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
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)−a1(n−1)−a2H(n−2)−…−akH(n−k)=0H(0)=b0H(1)=b1H(2)=b2…H(k−1)=bk−1
这是关于
H
(
n
)
H(n)
H(n)的递推方程，其中：
n
≥
k
,
a
k
≠
0
n geq k,a_k neq 0
n≥k,ak=0
2. 特征方程
递推方程的特征方程为
x
k
−
a
1
x
k
−
1
−
.
.
.
−
a
k
−
1
x
−
a
k
=
0
x^k-a_1x^{k-1}-…-a_{k-1}x-a_k=0
xk−a1xk−1−…−ak−1x−ak=0
特征方程的根为递推方程的特征根。
3. 递推方程的通解
若
q
1
,
q
2
,
.
.
.
,
q
k
q_1,q_2,…,q_k
q1,q2,…,qk是递推方程不等的特征根，则
c
1
q
1
n
+
c
2
q
2
n
+
.
.
.
+
c
k
q
k
n
c_1q_1^n+c_2q_2^n+…+c_kq_k^n
c1q1n+c2q2n+…+ckqkn是该递推方程的通解，其中
c
1
,
c
2
,
.
.
.
,
c
k
c_1,c_2,…,c_k
c1,c2,…,ck是任意常数。
若
q
q
q是递推方程的
i
i
i重特征根，则
(
c
1
+
c
2
n
+
.
.
.
+
c
k
n
i
−
1
)
q
n
(c_1+c_2n+…+c_kn^{i-1})q^n
(c1+c2n+…+ckni−1)qn是该递推方程的通解，其中
c
1
,
c
2
,
.
.
.
,
c
k
c_1,c_2,…,c_k
c1,c2,…,ck是任意常数。
将初始条件代入通解中，即可解得
c
1
,
c
2
,
.
.
.
,
c
k
c_1,c_2,…,c_k
c1,c2,…,ck，求出该递推方程的特解。
4. 例题
【例 1】求解递推方程
{
H
(
n
)
=
H
(
n
−
1
)
+
H
(
n
−
2
)
H
(
0
)
=
1
H
(
1
)
=
1
left{ begin{aligned} &H(n)=H(n-1)+H(n-2) \ &H(0)=1 \ &H(1)=1 \ end{aligned} right.
⎩
⎨
⎧H(n)=H(n−1)+H(n−2)H(0)=1H(1)=1
【解】特征方程为
x
2
−
x
−
1
=
0
x^2-x-1=0
x2−x−1=0，解得特征根为
x
1
=
1
+
5
2
,
x
2
=
1
−
5
2
x_1=frac{1+sqrt{5}}{2},x_2=frac{1-sqrt{5}}{2}
x1=21+5
,x2=21−5
，得到递推方程的通解
H
(
n
)
=
c
1
(
1
+
5
2
)
n
+
c
2
(
1
−
5
2
)
n
H(n)=c_1left(frac{1+sqrt{5}}{2}right)^n+c_2left(frac{1-sqrt{5}}{2}right)^n
H(n)=c1(21+5
)n+c2(21−5
)n
代入初值
H
(
0
)
=
1
,
H
(
1
)
=
1
H(0)=1,H(1)=1
H(0)=1,H(1)=1得到方程组
{
H
(
0
)
=
c
1
+
c
2
=
1
H
(
1
)
=
c
1
(
1
+
5
2
)
+
c
2
(
1
−
5
2
)
=
1
left{ begin{aligned} &H(0)=c_1+c_2=1 \ &H(1)=c_1left( frac{1+sqrt{5}}{2} right)+c_2left( frac{1-sqrt{5}}{2} right)=1 end{aligned} right.
⎩
⎨
⎧H(0)=c1+c2=1H(1)=c1(21+5
)+c2(21−5
)=1
解得
{
c
1
=
∣
1
1
1
1
−
5
2
∣
∣
1
1
1
+
5
2
1
−
5
2
∣
=
1
5
1
+
5
2
c
2
=
∣
1
1
1
+
5
2
1
∣
∣
1
1
1
+
5
2
1
−
5
2
∣
=
−
1
5
1
−
5
2
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.
⎩
⎨
⎧c1=
121+5
121−5
11121−5
=5
121+5
c2=
121+5
121−5
121+5
11
=−5
121−5
所以递推方程的通解为
H
(
n
)
=
1
5
(
1
+
5
2
)
n
+
1
−
1
5
(
1
−
5
2
)
n
+
1
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}
H(n)=5
1(21+5
)n+1−5
1(21−5
)n+1
【例 2】求解递推方程
{
H
(
n
)
−
3
H
(
n
−
1
)
+
4
H
(
n
−
3
)
=
0
H
(
0
)
=
1
H
(
1
)
=
0
H
(
2
)
=
0
left{ begin{aligned} &H(n)-3H(n-1)+4H(n-3)=0 \ &H(0)=1 \ &H(1)=0 \ &H(2)=0 end{aligned} right.
⎩
⎨
⎧H(n)−3H(n−1)+4H(n−3)=0H(0)=1H(1)=0H(2)=0
【解】特征方程为
x
3
−
3
x
2
+
4
=
0
x^3-3x^2+4=0
x3−3x2+4=0，解得特征根为
x
1
=
−
1
,
x
2
=
x
3
=
2
x_1=-1,x_2=x_3=2
x1=−1,x2=x3=2，得到递推方程的通解
H
(
n
)
=
(
c
1
+
c
2
n
)
⋅
2
n
+
c
3
⋅
(
−
1
)
n
H(n)=(c_1+c_2n)cdot2^n+c_3cdot(-1)^n
H(n)=(c1+c2n)⋅2n+c3⋅(−1)n
代入初值
H
(
0
)
=
1
,
H
(
1
)
=
0
,
H
(
2
)
=
0
H(0)=1,H(1)=0,H(2)=0
H(0)=1,H(1)=0,H(2)=0得到方程组
{
H
(
0
)
=
c
1
+
c
3
=
1
H
(
1
)
=
2
(
c
1
+
c
2
)
−
c
3
=
2
c
1
+
2
c
2
−
c
3
=
0
H
(
2
)
=
4
(
c
1
+
2
c
2
)
+
c
3
=
4
c
1
+
8
c
2
+
c
3
=
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.
⎩
⎨
⎧H(0)=c1+c3=1H(1)=2(c1+c2)−c3=2c1+2c2−c3=0H(2)=4(c1+2c2)+c3=4c1+8c2+c3=0
解得
{
c
1
=
∣
1
0
1
0
2
−
1
0
8
1
∣
∣
1
0
1
2
2
−
1
4
8
1
∣
=
5
9
c
2
=
∣
1
1
1
2
0
−
1
4
0
1
∣
∣
1
0
1
2
2
−
1
4
8
1
∣
=
−
1
3
c
3
=
∣
1
0
1
2
2
0
4
8
0
∣
∣
1
0
1
2
2
−
1
4
8
1
∣
=
4
9
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 & 1end{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 & 1end{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 & 1end{vmatrix}} = frac{4}{9} end{aligned} right.
⎩
⎨
⎧c1=
1240281−11
1000281−11
=95c2=
1240281−11
1241001−11
=−31c3=
1240281−11
124028100
=94
所以递推方程的通解为
H
(
n
)
=
(
5
9
−
1
3
n
)
2
n
+
4
9
(
−
1
)
n
H(n)=left(frac{5}{9}-frac{1}{3}nright)2^n+frac{4}{9}(-1)^n
H(n)=(95−31n)2n+94(−1)n
二、常系数线性非齐次递推方程
1. 定义
{
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
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)−a1(n−1)−a2H(n−2)−…−akH(n−k)=f(n)H(0)=b0H(1)=b1H(2)=b2…H(k−1)=bk−1
这是关于
H
(
n
)
H(n)
H(n)的递推方程，其中：
n
≥
k
,
a
k
≠
0
,
f
(
n
)
≠
0
n geq k,a_k neq 0,f(n) neq 0
n≥k,ak=0,f(n)=0
2. 特征方程
递推方程的特征方程为
x
k
−
a
1
x
k
−
1
−
.
.
.
−
a
k
−
1
x
−
a
k
=
0
x^k-a_1x^{k-1}-…-a_{k-1}x-a_k=0
xk−a1xk−1−…−ak−1x−ak=0
特征方程的根为递推方程的特征根。
3. 递推方程的通解
设
H
0
(
n
)
H_0(n)
H0(n)是对应齐次方程的通解，
H
∗
(
n
)
H^*(n)
H∗(n)是一个非齐次方程的特解，则该非齐次方程的通解为
H
(
n
)
=
H
0
(
n
)
+
H
∗
(
n
)
H(n)=H_0(n)+H^*(n)
H(n)=H0(n)+H∗(n)
4. 确定非齐次方程的特解
|
f ( n ) f(n) f(n) |
特解
H ∗ ( n ) H^*(n) H∗(n)的形式 |
|---|---|
|
a a a（ 1 1 1不是特征根） |
A A A |
|
a a a（ 1 1 1是特征根） |
n A nA nA |
|
a n + b an+b an+b （ 1 1 1不是特征根） |
A n + B An+B An+B |
|
a n + b an+b an+b （ 1 1 1是特征根） |
n ( A n + B ) n(An+B) n(An+B) |
|
a n 2 + b n + c an^2+bn+c an2+bn+c（ 1 1 1不是特征根） |
A n 2 + B n + C An^2+Bn+C An2+Bn+C |
|
a n 2 + b n + c an^2+bn+c an2+bn+c（ 1 1 1是特征根） |
n ( A n 2 + B n + C ) n(An^2+Bn+C) n(An2+Bn+C) |
|
a β n abeta^n aβn（ β beta β不是特征根） |
A β n Abeta^n Aβn |
|
a β n abeta^n aβn（ β beta β是 i i i重特征根） |
A n i β n An^ibeta^n Aniβn |
|
( a n + b ) β n (an+b)beta^n (an+b)βn（ β beta β不是特征根） |
( A n + B ) β n (An+B)beta^n (An+B)βn |
|
( a n + b ) β n (an+b)beta^n (an+b)βn（ β beta β是 i i i重特征根） |
( A n + B ) n i β n (An+B)n^ibeta^n (An+B)niβn |
5. 例题
【例 1】求解递推方程
{
H
(
n
)
=
H
(
n
−
1
)
+
n
−
1
H
(
1
)
=
0
left{ begin{aligned} &H(n)=H(n-1)+n-1 \ &H(1)=0 end{aligned} right.
{H(n)=H(n−1)+n−1H(1)=0
【解】特征方程为
x
2
−
x
=
0
x^2-x=0
x2−x=0，解得特征根为
x
1
=
1
,
x
2
=
0
x_1=1,x_2=0
x1=1,x2=0，得到对应齐次方程的通解
H
0
(
n
)
=
c
1
⋅
1
n
+
c
2
⋅
0
n
=
c
1
H_0(n)=c_1 cdot 1^n+c_2 cdot 0^n=c_1
H0(n)=c1⋅1n+c2⋅0n=c1
由于特征根中有
1
1
1，故设特解为
H
∗
(
n
)
=
n
(
A
n
+
B
)
=
A
n
2
+
B
n
H^*(n)=n(An+B)=An^2+Bn
H∗(n)=n(An+B)=An2+Bn
代入递推方程得
(
A
n
2
+
B
n
)
−
[
A
(
n
−
1
)
2
+
B
(
n
−
1
)
]
=
2
A
n
−
A
+
B
=
n
−
1
(An^2+Bn)-[A(n-1)^2+B(n-1)]=2An-A+B=n-1
(An2+Bn)−[A(n−1)2+B(n−1)]=2An−A+B=n−1
对比等号两边系数，得
A
=
1
2
,
B
=
−
1
2
A=frac{1}{2},B=-frac{1}{2}
A=21,B=−21，所以递推方程的通解为
H
(
n
)
=
H
0
(
n
)
+
H
∗
(
n
)
=
c
1
+
1
2
n
2
−
1
2
n
H(n)=H_0(n)+H^*(n)=c_1+frac{1}{2}n^2-frac{1}{2}n
H(n)=H0(n)+H∗(n)=c1+21n2−21n
代入初值条件
H
(
1
)
=
0
H(1)=0
H(1)=0，得
c
1
=
0
c_1=0
c1=0，最终得到
H
(
n
)
=
1
2
n
2
−
1
2
n
H(n)=frac{1}{2}n^2-frac{1}{2}n
H(n)=21n2−21n
【例 2】求解递推方程
{
H
(
n
)
=
2
H
(
n
−
1
)
+
1
H
(
1
)
=
1
left{ begin{aligned} &H(n)=2H(n-1)+1 \ &H(1)=1 end{aligned} right.
{H(n)=2H(n−1)+1H(1)=1
【解】特征方程为
x
2
−
2
x
=
0
x^2-2x=0
x2−2x=0，解得特征根为
x
1
=
2
,
x
2
=
0
x_1=2,x_2=0
x1=2,x2=0，得到对应齐次方程的通解
H
0
(
n
)
=
c
1
⋅
2
n
+
c
2
⋅
0
n
=
c
1
⋅
2
n
H_0(n)=c_1 cdot 2^n+c_2 cdot 0^n=c_1 cdot 2^n
H0(n)=c1⋅2n+c2⋅0n=c1⋅2n
设特解为
H
∗
(
n
)
=
A
H^*(n)=A
H∗(n)=A，代入递推方程得
A
=
2
A
+
1
A=2A+1
A=2A+1，解得
A
=
−
1
A=-1
A=−1，所以递推方程的通解为
H
(
n
)
=
H
0
(
n
)
+
H
∗
(
n
)
=
c
1
⋅
2
n
−
1
H(n)=H_0(n)+H^*(n)=c_1 cdot 2^n-1
H(n)=H0(n)+H∗(n)=c1⋅2n−1
代入初值条件
H
(
1
)
=
1
H(1)=1
H(1)=1，得
c
1
=
1
c_1=1
c1=1，最终得到
H
(
n
)
=
2
n
−
1
H(n)=2^n-1
H(n)=2n−1
【例 3】求解递推方程
{
H
(
n
)
−
4
H
(
n
−
1
)
+
4
H
(
n
−
2
)
=
2
n
H
(
0
)
=
1
H
(
1
)
=
5
left{ begin{aligned} &H(n)-4H(n-1)+4H(n-2)=2^n \ &H(0)=1 \ &H(1)=5 end{aligned} right.
⎩
⎨
⎧H(n)−4H(n−1)+4H(n−2)=2nH(0)=1H(1)=5
【解】特征方程为
x
2
−
4
x
+
4
=
0
x^2-4x+4=0
x2−4x+4=0，解得特征根为
x
1
=
x
2
=
2
x_1=x_2=2
x1=x2=2，得到对应齐次方程的通解
H
0
(
n
)
=
(
c
1
+
c
2
n
)
⋅
2
n
H_0(n)=(c_1+c_2n) cdot 2^n
H0(n)=(c1+c2n)⋅2n
由于
2
2
2为二重特征根，故设特解为
H
∗
(
n
)
=
n
2
A
⋅
2
n
H^*(n)=n^2A cdot 2^n
H∗(n)=n2A⋅2n
代入递推方程得
n
2
A
⋅
2
n
−
4
(
n
−
1
)
2
A
⋅
2
n
−
1
+
4
(
n
−
2
)
2
A
⋅
2
n
−
2
=
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
n2A⋅2n−4(n−1)2A⋅2n−1+4(n−2)2A⋅2n−2=2n
解得
A
=
1
2
A=frac{1}{2}
A=21，所以递推方程的通解为
H
(
n
)
=
H
0
(
n
)
+
H
∗
(
n
)
=
(
c
1
+
c
2
n
)
⋅
2
n
+
n
2
⋅
2
n
−
1
H(n)=H_0(n)+H^*(n)=(c_1+c_2n) cdot 2^n+n^2 cdot 2^{n-1}
H(n)=H0(n)+H∗(n)=(c1+c2n)⋅2n+n2⋅2n−1
代入初值条件得
{
H
(
0
)
=
c
1
=
1
H
(
1
)
=
2
(
c
1
+
c
2
)
+
1
=
5
left{ begin{aligned} &H(0)= c_1 = 1\ &H(1)= 2(c_1+c_2)+1=5 end{aligned} right.
{H(0)=c1=1H(1)=2(c1+c2)+1=5
解得
c
1
=
1
,
c
2
=
1
c_1=1,c_2=1
c1=1,c2=1，最终得到
H
(
n
)
=
(
1
+
n
)
⋅
2
n
+
n
2
⋅
2
n
−
1
H(n)=(1+n) cdot 2^n+n^2 cdot 2^{n-1}
H(n)=(1+n)⋅2n+n2⋅2n−1
三、其他解法
以上方法只适用于常系数线性递推方程，对于变系数递推方程和特征根为虚数的情况，还可以使用以下方法求解。
1. 数学归纳法（用于证明）
当待证结论为一阶形式时，使用第一数学归纳法：
{
（
1
）
验证
n
=
1
时，命题
H
(
n
)
正确
（
2
）
假设
n
=
k
(
k
≥
2
)
时，命题
H
(
n
)
正确
（
3
）
证明
n
=
k
+
1
时，命题
H
(
n
)
正确
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.
⎩
⎨
⎧（1）（2）（3）验证n=1时，命题H(n)正确假设n=k(k≥2)时，命题H(n)正确证明n=k+1时，命题H(n)正确
当待证结论为二阶形式时，使用第二数学归纳法：
{
（
1
）
验证
n
=
1
和
n
=
2
时，命题
H
(
n
)
均正确
（
2
）
假设
n
⎩
⎨
⎧（1）（2）（3）验证n=1和n=2时，命题H(n)均正确假设nk(k≥3)时，命题H(n)正确证明n=k时，命题H(n)正确
2. 迭代归纳法
【例 1】求解递推方程
{
H
(
n
)
−
n
H
(
n
−
1
)
=
n
!
H
(
0
)
=
2
left{ begin{aligned} &H(n)-nH(n-1)=n! \ &H(0)=2 end{aligned} right.
{H(n)−nH(n−1)=n!H(0)=2
【解】由迭代法得
H
(
n
)
=
n
!
+
n
H
(
n
−
1
)
=
n
!
+
n
[
(
n
−
1
)
!
+
(
n
−
1
)
H
(
n
−
2
)
]
=
n
!
+
n
(
n
−
1
)
!
+
n
(
n
−
1
)
H
(
n
−
2
)
=
2
n
!
+
n
(
n
−
1
)
H
(
n
−
2
)
=
2
n
!
+
n
(
n
−
1
)
[
(
n
−
2
)
!
+
(
n
−
2
)
H
(
n
−
3
)
]
=
3
n
!
+
n
(
n
−
1
)
(
n
−
2
)
H
(
n
−
3
)
=
.
.
.
=
n
⋅
n
!
+
n
!
⋅
H
(
0
)
=
n
⋅
n
!
+
n
!
⋅
2
=
(
n
+
2
)
⋅
n
!
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}
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⋅n!+n!⋅H(0)=n⋅n!+n!⋅2=(n+2)⋅n!
为确保结果的正确性，使用数学归纳法进行验证：
（1）当
n
=
0
n=0
n=0时，
H
(
0
)
=
(
0
+
2
)
⋅
0
!
=
2
H(0)=(0+2) cdot 0!=2
H(0)=(0+2)⋅0!=2，说明命题
H
(
n
)
H(n)
H(n)正确；
（2）假设
n
=
k
(
k
≥
1
)
n=k(k geq 1)
n=k(k≥1)时，命题
H
(
n
)
H(n)
H(n)正确；
（3）当
n
=
k
+
1
n=k+1
n=k+1时，
H
(
k
+
1
)
=
(
k
+
1
)
!
+
(
k
+
1
)
H
(
k
)
=
(
k
+
1
)
[
k
!
+
H
(
k
)
]
=
(
k
+
1
)
[
k
!
+
(
k
+
2
)
⋅
k
!
]
=
(
k
+
1
)
[
1
+
(
k
+
2
)
]
k
!
=
[
(
k
+
1
)
+
2
)
]
(
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}
H(k+1)=(k+1)!+(k+1)H(k)=(k+1)[k!+H(k)]=(k+1)[k!+(k+2)⋅k!]=(k+1)[1+(k+2)]k!=[(k+1)+2)](k+1)!
说明结果正确。
【例 2】求解递推方程
{
(
n
−
1
)
H
(
n
)
−
n
H
(
n
−
1
)
=
0
H
(
1
)
=
1
left{ begin{aligned} &(n-1)H(n)-nH(n-1)=0 \ &H(1)=1 end{aligned} right.
{(n−1)H(n)−nH(n−1)=0H(1)=1
【解】由迭代法得
H
(
n
)
=
n
n
−
1
H
(
n
−
1
)
=
n
n
−
1
n
−
1
n
−
2
H
(
n
−
2
)
=
n
n
−
1
n
−
1
n
−
2
n
−
2
n
−
3
H
(
n
−
3
)
=
.
.
.
=
n
n
−
1
n
−
1
n
−
2
n
−
2
n
−
3
⋅
⋅
⋅
2
1
H
(
1
)
=
n
!
(
n
−
1
)
!
H
(
1
)
=
n
⋅
H
(
1
)
=
n
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}
H(n)=n−1nH(n−1)=n−1nn−2n−1H(n−2)=n−1nn−2n−1n−3n−2H(n−3)=…=n−1nn−2n−1n−3n−2⋅⋅⋅12H(1)=(n−1)!n!H(1)=n⋅H(1)=n
由数学归纳法验证可知结果正确。
【例 3】求解递推方程
{
(
n
−
1
)
H
(
n
)
−
n
H
(
n
−
1
)
=
1
H
(
1
)
=
1
left{ begin{aligned} &(n-1)H(n)-nH(n-1)=1 \ &H(1)=1 end{aligned} right.
{(n−1)H(n)−nH(n−1)=1H(1)=1
【解】这是一个非齐次变系数递推方程，先解对应的齐次方程
(
n
−
1
)
H
(
n
)
−
n
H
(
n
−
1
)
=
0
(n-1)H(n)-nH(n-1)=0
(n−1)H(n)−nH(n−1)=0，由迭代法解得
H
(
n
)
=
n
⋅
H
(
1
)
H(n)=n cdot H(1)
H(n)=n⋅H(1)，即
H
(
n
)
n
=
H
(
1
)
frac{H(n)}{n}=H(1)
nH(n)=H(1)。现将原非齐次方程凑成
H
(
n
)
n
frac{H(n)}{n}
nH(n)的形式，等式两边同除
n
(
n
−
1
)
n(n-1)
n(n−1)可得
H
(
n
)
n
−
H
(
n
−
1
)
n
−
1
=
1
n
(
n
−
1
)
frac{H(n)}{n}-frac{H(n-1)}{n-1}=frac{1}{n(n-1)}
nH(n)−n−1H(n−1)=n(n−1)1
令
T
(
n
)
=
H
(
n
)
n
T(n)=frac{H(n)}{n}
T(n)=nH(n)，得到一个新的递推方程
{
T
(
n
)
−
T
(
n
−
1
)
=
1
n
(
n
−
1
)
T
(
1
)
=
1
left{ begin{aligned} &T(n)-T(n-1)=frac{1}{n(n-1)} \ &T(1)=1 end{aligned} right.
⎩
⎨
⎧T(n)−T(n−1)=n(n−1)1T(1)=1
所以有
T
(
n
)
=
[
T
(
n
)
−
T
(
n
−
1
)
]
+
[
T
(
n
−
1
)
−
T
(
n
−
2
)
]
+
.
.
.
+
[
T
(
2
)
−
T
(
1
)
]
+
T
(
1
)
=
∑
k
=
2
n
[
T
(
k
)
−
T
(
k
−
1
)
]
+
T
(
1
)
=
1
+
∑
k
=
2
n
1
k
(
k
−
1
)
=
1
+
(
1
−
1
2
+
1
2
−
1
3
+
.
.
.
−
1
n
−
1
+
1
n
−
1
−
1
n
)
=
2
−
1
n
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}^nfrac{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}
T(n)=[T(n)−T(n−1)]+[T(n−1)−T(n−2)]+…+[T(2)−T(1)]+T(1)=k=2∑n[T(k)−T(k−1)]+T(1)=1+k=2∑nk(k−1)1=1+(1−21+21−31+…−n−11+n−11−n1)=2−n1
即：
H
(
n
)
=
2
n
−
1
H(n)=2n-1
H(n)=2n−1
【例 4】求解递推方程
{
(
n
+
2
)
H
(
n
)
−
(
n
−
1
)
H
(
n
−
1
)
=
1
H
(
1
)
=
1
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)=1H(1)=1
【解】这是一个非齐次变系数递推方程，先解对应的齐次方程
(
n
+
2
)
H
(
n
)
−
(
n
−
1
)
H
(
n
−
1
)
=
0
(n+2)H(n)-(n-1)H(n-1)=0
(n+2)H(n)−(n−1)H(n−1)=0，由迭代法得
H
(
n
)
=
n
−
1
n
+
2
H
(
n
−
1
)
=
n
−
1
n
+
2
n
−
2
n
+
1
H
(
n
−
2
)
=
n
−
1
n
+
2
n
−
2
n
+
1
n
−
3
n
H
(
n
−
3
)
=
.
.
.
=
n
−
1
n
+
2
n
−
2
n
+
1
n
−
3
n
⋅
⋅
⋅
1
4
H
(
1
)
=
(
n
−
1
)
!
(
n
+
2
)
!
6
H
(
1
)
=
6
(
n
−
1
)
!
(
n
+
2
)
!
H
(
1
)
=
6
n
(
n
+
1
)
(
n
+
2
)
H
(
1
)
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) \ &=6frac{(n-1)!}{(n+2)!}H(1) \ &=frac{6}{n(n+1)(n+2)}H(1) end{aligned}
H(n)=n+2n−1H(n−1)=n+2n−1n+1n−2H(n−2)=n+2n−1n+1n−2nn−3H(n−3)=…=n+2n−1n+1n−2nn−3⋅⋅⋅41H(1)=6(n+2)!(n−1)!H(1)=6(n+2)!(n−1)!H(1)=n(n+1)(n+2)6H(1)
即
n
(
n
+
1
)
(
n
+
2
)
H
(
n
)
=
6
H
(
1
)
n(n+1)(n+2)H(n)=6H(1)
n(n+1)(n+2)H(n)=6H(1)，现将原非齐次方程凑成
n
(
n
+
1
)
(
n
+
2
)
H
(
n
)
n(n+1)(n+2)H(n)
n(n+1)(n+2)H(n)的形式，等式两边同乘
n
(
n
+
1
)
n(n+1)
n(n+1)可得
n
(
n
+
1
)
(
n
+
2
)
H
(
n
)
−
(
n
−
1
)
n
(
n
+
1
)
H
(
n
−
1
)
=
n
(
n
+
1
)
n(n+1)(n+2)H(n)-(n-1)n(n+1)H(n-1)=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
)
T(n)=n(n+1)(n+2)H(n)
T(n)=n(n+1)(n+2)H(n)，得到一个新的递推方程
{
T
(
n
)
−
T
(
n
−
1
)
=
n
(
n
+
1
)
T
(
1
)
=
6
left{ begin{aligned} &T(n)-T(n-1)=n(n+1) \ &T(1)=6 end{aligned} right.
{T(n)−T(n−1)=n(n+1)T(1)=6
所以有
T
(
n
)
=
∑
k
=
2
n
[
T
(
k
)
−
T
(
k
−
1
)
]
+
T
(
1
)
=
6
+
∑
k
=
2
n
k
(
k
+
1
)
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}
T(n)=k=2∑n[T(k)−T(k−1)]+T(1)=6+k=2∑nk(k+1)
即
H
(
n
)
=
1
n
(
n
+
1
)
(
n
+
2
)
[
6
+
∑
k
=
2
n
k
(
k
+
1
)
]
H(n)=frac{1}{n(n+1)(n+2)}[6+sum_{k=2}^n k(k+1)]
H(n)=n(n+1)(n+2)1[6+k=2∑nk(k+1)]
【例 5】求解递推方程
{
n
H
(
n
)
−
H
(
n
−
1
)
=
1
H
(
1
)
=
1
left{ begin{aligned} &nH(n)-H(n-1)=1 \ &H(1)=1 end{aligned} right.
{nH(n)−H(n−1)=1H(1)=1
【解】这是一个非齐次变系数递推方程，先解对应的齐次方程
n
H
(
n
)
−
H
(
n
−
1
)
=
0
nH(n)-H(n-1)=0
nH(n)−H(n−1)=0，由迭代法得
H
(
n
)
=
1
n
H
(
n
−
1
)
=
1
n
1
n
−
1
H
(
n
−
2
)
=
1
n
1
n
−
1
1
n
−
2
H
(
n
−
3
)
=
.
.
.
=
1
n
!
H
(
1
)
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}
H(n)=n1H(n−1)=n1n−11H(n−2)=n1n−11n−21H(n−3)=…=n!1H(1)
即
n
!
H
(
n
)
=
H
(
1
)
n!H(n)=H(1)
n!H(n)=H(1)，现将原非齐次方程凑成
n
!
H
(
n
)
n!H(n)
n!H(n)的形式，等式两边同乘
(
n
−
1
)
!
(n-1)!
(n−1)!可得
n
!
H
(
n
)
−
(
n
−
1
)
!
H
(
n
−
1
)
=
(
n
−
1
)
!
n!H(n)-(n-1)!H(n-1)=(n-1)!
n!H(n)−(n−1)!H(n−1)=(n−1)!
令
T
(
n
)
=
n
!
H
(
n
)
T(n)=n!H(n)
T(n)=n!H(n)，得到一个新的递推方程
{
T
(
n
)
−
T
(
n
−
1
)
=
(
n
−
1
)
!
T
(
1
)
=
1
left{ begin{aligned} &T(n)-T(n-1)=(n-1)! \ &T(1)=1 end{aligned} right.
{T(n)−T(n−1)=(n−1)!T(1)=1
所以有
T
(
n
)
=
∑
k
=
2
n
[
T
(
k
)
−
T
(
k
−
1
)
]
+
T
(
1
)
=
1
+
∑
k
=
2
n
(
k
−
1
)
!
begin{aligned} T(n)&=sum_{k=2}^n[T(k)-T(k-1)]+T(1) \ &=1+sum_{k=2}^n (k-1)! \ end{aligned}
T(n)=k=2∑n[T(k)−T(k−1)]+T(1)=1+k=2∑n(k−1)!
即
H
(
n
)
=
1
n
!
+
1
!
n
!
+
2
!
n
!
+
.
.
.
+
(
n
−
1
)
!
n
!
H(n)=frac{1}{n!}+frac{1!}{n!}+frac{2!}{n!}+…+frac{(n-1)!}{n!}
H(n)=n!1+n!1!+n!2!+…+n!(n−1)!
【例 6】设
n
n
n阶矩阵
A
A
A和
B
B
B，已知
A
B
=
c
B
（
c
为常数）
AB=cB（c为常数）
AB=cB（c为常数），求证：
A
n
B
=
c
n
B
A^nB=c^nB
AnB=cnB。
【证】使用迭代法：
A
n
B
=
A
n
−
1
⋅
A
B
=
A
n
−
1
⋅
c
B
=
c
⋅
A
n
−
1
B
=
c
A
n
−
2
⋅
A
B
=
c
A
n
−
2
⋅
c
B
=
c
2
⋅
A
n
−
2
B
=
.
.
.
=
c
n
−
1
⋅
A
B
=
c
n
−
1
⋅
c
B
=
c
n
B
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}
AnB=An−1⋅AB=An−1⋅cB=c⋅An−1B=cAn−2⋅AB=cAn−2⋅cB=c2⋅An−2B=…=cn−1⋅AB=cn−1⋅cB=cnB
3. 差消法
有些高阶递推方程，需要先使用差消法将其转化为一阶递推方程再求解更方便。
【例 1】求解递推方程
{
H
(
n
)
=
(
n
−
1
)
[
H
(
n
−
1
)
+
H
(
n
−
2
)
]
H
(
1
)
=
0
H
(
2
)
=
1
left{ begin{aligned} &H(n)=(n-1)[H(n-1)+H(n-2)] \ &H(1)=0 \ &H(2)=1 end{aligned} right.
⎩
⎨
⎧H(n)=(n−1)[H(n−1)+H(n−2)]H(1)=0H(2)=1
【解】由于直接迭代该二阶递推方程比较繁琐，因此使用差消法得
H
(
n
)
−
n
H
(
n
−
1
)
=
−
[
H
(
n
−
1
)
−
(
n
−
1
)
H
(
n
−
2
)
]
=
(
−
1
)
2
⋅
[
H
(
n
−
2
)
−
(
n
−
2
)
H
(
n
−
3
)
]
=
(
−
1
)
3
⋅
[
H
(
n
−
3
)
−
(
n
−
3
)
H
(
n
−
4
)
]
=
.
.
.
=
(
−
1
)
n
−
2
⋅
[
H
(
2
)
−
2
H
(
1
)
]
=
(
−
1
)
n
−
2
=
(
−
1
)
n
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}
H(n)−nH(n−1)=−[H(n−1)−(n−1)H(n−2)]=(−1)2⋅[H(n−2)−(n−2)H(n−3)]=(−1)3⋅[H(n−3)−(n−3)H(n−4)]=…=(−1)n−2⋅[H(2)−2H(1)]=(−1)n−2=(−1)n
此时二阶递推方程转化为一阶递推方程为
{
H
(
n
)
−
n
H
(
n
−
1
)
=
(
−
1
)
n
H
(
1
)
=
0
left{ begin{aligned} &H(n)-nH(n-1)=(-1)^n \ &H(1)=0 end{aligned} right.
{H(n)−nH(n−1)=(−1)nH(1)=0
这是一个变系数的递推方程，使用迭代法得
H
(
n
)
=
n
H
(
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
]
⋅
H
(
1
)
+
[
n
(
n
−
1
)
⋅
⋅
⋅
3
]
⋅
(
−
1
)
2
+
[
n
(
n
−
1
)
⋅
⋅
⋅
4
]
⋅
(
−
1
)
3
+
.
.
.
+
n
(
−
1
)
n
−
1
+
(
−
1
)
n
=
[
n
(
n
−
1
)
⋅
⋅
⋅
3
]
⋅
(
−
1
)
2
+
[
n
(
n
−
1
)
⋅
⋅
⋅
4
]
⋅
(
−
1
)
3
+
.
.
.
+
n
(
−
1
)
n
−
1
+
(
−
1
)
n
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}
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]⋅H(1)+[n(n−1)⋅⋅⋅3]⋅(−1)2+[n(n−1)⋅⋅⋅4]⋅(−1)3+…+n(−1)n−1+(−1)n=[n(n−1)⋅⋅⋅3]⋅(−1)2+[n(n−1)⋅⋅⋅4]⋅(−1)3+…+n(−1)n−1+(−1)n
4. 一些技巧
【例 1】求解递推方程
{
H
(
n
)
=
(
1
−
a
)
H
(
n
−
1
)
+
a
H
(
n
−
2
)
H
(
1
)
=
1
−
a
H
(
2
)
=
1
−
a
+
a
2
(
a
≠
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)
⎩
⎨
⎧H(n)=(1−a)H(n−1)+aH(n−2)H(1)=1−aH(2)=1−a+a2(a=1)
【解】该题可以使用公式法求解，其特征方程为
(
q
−
1
)
(
q
−
a
)
=
0
(q-1)(q-a)=0
(q−1)(q−a)=0。现在使用另一种方法来解决。原方程可变形为
H
(
n
)
−
H
(
n
−
1
)
=
−
a
[
H
(
n
−
1
)
−
H
(
n
−
2
)
]
begin{aligned} H(n)-H(n-1)=-a[H(n-1)-H(n-2)] end{aligned}
H(n)−H(n−1)=−a[H(n−1)−H(n−2)]
令
T
(
n
)
=
H
(
n
)
−
H
(
n
−
1
)
(
n
≥
2
)
T(n)=H(n)-H(n-1)(n geq 2)
T(n)=H(n)−H(n−1)(n≥2)，则得到一个新的递推方程
{
T
(
n
)
=
−
a
T
(
n
−
1
)
T
(
2
)
=
a
2
(
a
≠
1
,
n
≥
3
)
left{ begin{aligned} &T(n)=-aT(n-1) \ &T(2)=a^2 end{aligned} right. (a neq 1,n geq 3)
{T(n)=−aT(n−1)T(2)=a2(a=1,n≥3)
注意到
T
(
n
)
T(n)
T(n)是一个公比为
−
a
-a
−a的等比数列，所以通项公式为
T
(
n
)
=
T
(
2
)
(
−
a
)
n
−
2
(
n
≥
3
)
T(n)=T(2)(-a)^{n-2}(n geq 3)
T(n)=T(2)(−a)n−2(n≥3)，即
T
(
n
)
=
H
(
n
)
−
H
(
n
−
1
)
=
a
2
⋅
(
−
a
)
n
−
2
=
(
−
a
)
2
⋅
(
−
a
)
n
−
2
=
(
−
a
)
n
T(n)=H(n)-H(n-1)=a^2 cdot (-a)^{n-2}=(-a)^2 cdot (-a)^{n-2}=(-a)^n
T(n)=H(n)−H(n−1)=a2⋅(−a)n−2=(−a)2⋅(−a)n−2=(−a)n
所以有
H
(
n
)
=
∑
k
=
2
n
[
H
(
k
)
−
H
(
k
−
1
)
]
+
H
(
1
)
=
1
−
a
+
∑
k
=
2
n
[
(
−
a
)
k
]
=
1
−
a
+
a
2
−
a
3
+
.
.
.
+
(
−
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}
H(n)=k=2∑n[H(k)−H(k−1)]+H(1)=1−a+k=2∑n[(−a)k]=1−a+a2−a3+…+(−a)n
【例 2】求解递推方程
{
H
(
n
)
=
H
(
n
−
1
)
−
H
(
n
−
2
)
H
(
1
)
=
1
H
(
2
)
=
0
left{ begin{aligned} &H(n)=H(n-1)-H(n-2) \ &H(1)=1 \ &H(2)=0 end{aligned} right.
⎩
⎨
⎧H(n)=H(n−1)−H(n−2)H(1)=1H(2)=0
【解】由于特征方程为虚数根（也同时说明解可能具有周期性），所以难以使用公式求解。原方程可变形为
H
(
n
)
=
H
(
n
−
1
)
−
H
(
n
−
2
)
=
[
H
(
n
−
2
)
−
H
(
n
−
3
)
]
−
H
(
n
−
2
)
=
−
H
(
n
−
3
)
begin{aligned} H(n)&=H(n-1)-H(n-2) \ &=[H(n-2)-H(n-3)]-H(n-2) \ &=-H(n-3) end{aligned}
H(n)=H(n−1)−H(n−2)=[H(n−2)−H(n−3)]−H(n−2)=−H(n−3)
所以递推方程变为
{
H
(
n
)
=
−
H
(
n
−
3
)
H
(
1
)
=
1
H
(
2
)
=
0
H
(
3
)
=
−
1
left{ begin{aligned} &H(n)=-H(n-3) \ &H(1)=1 \ &H(2)=0 \ &H(3)=-1 end{aligned} right.
⎩
⎨
⎧H(n)=−H(n−3)H(1)=1H(2)=0H(3)=−1
显然，这是一个分为三段的周期数列，即
{
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
,
.
.
.
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(1)=1,H(2)=0,H(3)=−1,H(4)=−1,H(5)=0,H(6)=1,H(7)=1,…H(8)=0,…H(9)=−1,…
写成表达式为
H
(
n
)
=
{
(
−
1
)
k
+
1
,
n
=
3
k
−
2
0
,
n
=
3
k
−
1
(
−
1
)
k
,
n
=
3
k
(
k
≥
1
)
H(n)= begin{cases} (-1)^{k+1},&n=3k-2 \ 0,&n=3k-1 \ (-1)^k,&n=3k \ end{cases} (k geq 1)
H(n)=⎩
⎨
⎧(−1)k+1,0,(−1)k,n=3k−2n=3k−1n=3k(k≥1)
参考资料：《离散数学第2版（屈婉玲）》《离散数学学习指导与习题解析第2版（屈婉玲）》
服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net
