1
2.2 用生成函数求解递归方程
2.2.1 生成函数及其性质
一、生成函数的定义
定义2.1 令 ,,,210a a a 是一个实数序列，构造如下的函数：
k
k k z
a
z a z a a z G ∑∞
==
+++=0
2
210)( （2.2.1）
则函数)(z G 称为序列 ,,,210a a a 的生成函数。
例：函数
n
n n n n n n x C x C x C C x ++++=+ 2210)1(
则函数n x )1(+便是序列n
n
n n n C C C C ,,,,210 的生成函数。 二、生成函数的性质
1. 加法 设k
k k z
a
z G ∑∞
==
)(是序列 ,,,210a a a 的生成函数，k
k k z
b z H ∑∞
==
)(是序列
,,,210b b b 的生成函数，则)()(z H z G βα+
k
k k k
k k z
b z
a
z H z G ∑∑∞
=∞
=+=+0
)()(β
α
βα
k k k k
z b a
)(0
∑∞
=+=
βα
（2.2.2）
是序列 ,,,221100b a b a b a βαβαβα+++的生成函数。
2．移位 设k
k k z
a
z G ∑∞
==
)(是序列 ,,,210a a a 的生成函数，则)(z G z m
k
m
k m k m
z
a
z G z ∑∞
=-=
)( （2.2.3）
是序列 ,,,,0,,0210a a a 的生成函数。
3．乘法 设k
k k z a
z G ∑∞
==0
)(是序列 ,,,210a a a 的生成函数，k
k k z
b z H ∑∞
==
)(是序列
2
,,,210b b b 的生成函数，则)()(z H z G
)()()()(22102210 ++++++=z b z b b z a z a a z H z G
++++++=2021120011000)()(z b a b a b a z b a b a b a
k
k k z
c
∑∞
==
（2.2.4）
是序列 ,,,210c c c 的生成函数，其中，k
n n
k k n b
a c -=∑=
4. z 变换 设k
k k z
a
z G ∑∞
==
)(是序列 ,,,210a a a 的生成函数，则)(z c G
++++=332210)()()()(z c a z c a z c a a z c G
++++=33322210z a c z a c z a c a （2.2.5）
是序列 ,,,2210a c a c a 的生成函数。
特别地，有：
++++=-3322111
z c z c z c z
c （2.2.6）
所以，
z
c -11
是序列 ,,,,132c c c 的生成函数。 当1=c 时，有：
+++=-2111
z z z
（2.2.7）
则
z
-11
是序列1,1,1,…的生成函数。 利用：
+++=-+44220))()((2
1
z a z a a z G z G （2.2.8）
可以去掉级数中的奇数项；同样，利用
+++=--55331))()((2
1
z a z a z a z G z G （2.2.9）
可以去掉级数中的偶数项。
5．微分和积分 设k
k k z
a
z G ∑∞
==
)(是序列 ,,,210a a a 的生成函数，对)(z G 求导数
3
k
k k z
a
k z a z a a z G ∑∞
=++=
+++=0
12
321)1(32)(' （2.2.10）
显然，)('z G 是序列 ,3,2,321a a a 的生成函数。同样，对)(z G 求积分
k k k z
z a k
z a z a z a t d t G ∑
?
∞
=-=
+++=1
1322100
1
3
1
21)( （2.2.11）
则积分?
z
t d t G 0
)(是 ,3
1
,21,210a a a 的生成函数。
如果对（2.2.7）式求导数，可得：
∑∞
=+=
+++=-0
2
2
)1(321)1(1k k
z
k z z z （2.2.12）
则
2
)1(1z -是算术级数1,2,3…的生成函数。
如果对（2.2.7）式求积分，可得：
∑∞
==+++=-1
321
3
12111ln k k
z
k z z z z （2.2.13）
则z -11ln
是调和数 ,3
1
,21,1的生成函数。 2.2.2 用生成函数求解递归方程
例2.1 汉诺塔（Hanoi ）问题。
宝石针的编号为A 、B 、C ，A 针串着64片金盘。希望把它们移到B 针或C 针。有可n 是金盘的数量，)(n h 是移动n 个金盘的移动次数
1． 当1=n 时， )1(h =1。 2． 当2=n 时， 1)1(2)2(+=h h 。 3． 当3=n 时， 1)2(2)3(+=h h 。 递归关系式：
??
?=+-=1
)1(1
)1(2)(h n h n h （2.2.14）
用)(n h 作为系数，构造一个生成函数：
+++=32)3()2()1()(x h x h x h x G
4
∑∞
==
1
)(k k
x
k h
令
---+++=-3232)2(2)1(2)3()2()1()(2)(x h x h x h x h x h x G x x G
+-+-+=32))2(2)3(())1(2)2(()1(x h h x h h x h
由（2.2.14）及（2.2.7）式得：
+++=-32)()21(x x x x G x
x
x -=1 所以，
)
21()1()(x x x
x G --=
令：
)21()1()(x B x A x G -+-=
)
21()1(2x x Bx
B Ax A ---+-=
有：
120
=--=+B A B A
求得1,1=-=B A 。所以：
)
1(1)21(1)(x x x G ---=
)1()2221(323322 ++++-++++=x x x x x x +-+-+-=3322)12()12()12(x x x
k k k
x )12
(1
-=
∑∞
=
12)(-=n n h ，它是式中第n 项的系数。当64=n 时，移动次数为1264-。
例2.2 菲波那契序列问题。
)(n t 、)(n T 、)(n f 表示第n 个月小兔子、大兔子的数目，及第n 个月兔子的总数目。
则：
)1()1()(-+-=n t n T n T （2.2.15） )1()(-=n T n t
（2.2.16） )()()(n t n T n f +=
（2.2.17）
第一式：第n 个月大兔子的数量，为前一个月大兔子的数量加上前一个月小兔子的数量；第二式：第n 个月小兔子的数量，为前一个月大兔子的数量；
第三式：表示第n 个月兔子的总量为该月大兔子的数量及小兔子的数量之和。递归方程：
5
?
?
?==-+-=1)2()1()
2()1()(f f n f n f n f （2.2.18）
用)(n f 作为系数，构造生成函数：
+++=32)3()2()1()(x f x f x f x F
∑∞
==
1
)(k k
x
k f
令：
)()()(2x F x x F x x F --
))1(())2()1(()3()2()1(2232 +-++-+++=x f x x f x f x x f x f x f +--+-+=32))1()2()3(())1()2(()1(x f f f x f f x f
x =
所以，有：
2
1)(x
x x x F --=
4
5
412
-
++-=
x x x 2
2
52121??
?
??-??? ?
?
+-=
x x
??
? ?
?
+
+??? ?
?
-
+-=
51(2151(21x x x
)
51(2
1)
51(21+++-+=x B x A
?
?
? ??++??? ??-+-++++
=
51(2151(21)51(21
)51(21x x B x B A x A 有：0)51()51(,1=-++-=+B A B A 解得：)51(5
21,
)51(5
21+
-=
-
=
B A
把A 、B 代入)(x F ，得到：
???
? ??+++-
-+-=512515125151)(x x x F
6
)1
5211
1
5211(
51
+--
---
=
x x 令)51(2
11
52+=
-=α，)51(2
11
52-=
+-=β
则有：
+-+-=
222)(()((5
1)(x x x F βαβα
所以，第n 项系数为：
)(5
1)(n n n f βα-=
2.3 用特征方程求解递归方程
2.3.1 k 阶常系数线性齐次递归方程
一、k 阶常系数线性齐次递归方程
1、递归方程的形式：
?
?
?<≤=-+-+-=k i b i f k n f a n f a n f a n f i k 0)()
()2()1()(21 （2.3.1）
2、递归方程的特征方程
n x 取代)(n f ：
k n k n n n x a x a x a x ---+++= 2211
两边分别除以k n x -，可得：
k k k k a x a x a x +++=-- 2211
把上式写成：
02211=------k k k k a x a x a x
（2.3.2）
则式（2.3.2）称为递归方程（2.3.1）的特征方程。 二、k 阶常系数线性齐次递归方程的求解
1、k q q q ,,,21 是特征方程的k 个互不相同的根。则递归方程（2.3.1）的通解为：
n
k
k n n q c q c q c n f +++= 2211)( （2.3.3）
7
2、特征方程的k 个根中有r 个重根11,,,-++r i i i q q q ，递归方程（2.3.1）的通解形式为：
n
k
k n i r r i i i n i i n q c q n c n c c q c q c n f ++++++++=--++-- )()(1111111 （2.3.4）
在（2.3.3）及（2.3.4）中，k c c c ,,,21 为待定系数。
3、求解过程：把递归方程的初始条件代入（2.3.3）或（2.3.4）中，建立联立方程，确定系数k c c c ,,,21 ，从而可求出通解)(n f 。
例2.3 三阶常系数线性齐次递归方程如下：
?
?
?===---=10)2(2)1(0)0()3(6)2(11)1(6)(f f f n f n f n f n f ＋－ 解 特征方程为：
0611623=-+-x x x
把方程改写成：
062933223=-++--x x x x x
对特征方程进行因式分解，得：
0)3()2()1(=---x x x
则有特征根：
32
1
321===q q q
所以，递归方程的通解为：
n
n n q c q c q c n f 3
32211)(++= n n c c c 32321++=
由初始条件得：
0)0(321=++=c c c f 232)1(321=++=c c c f
1094)2(321=++=c c c f
解此联立方程，得：
22
321=-==c c c
则递归方程的解为：
)23(2)(n n n f -=
例2.4 三阶常系数线性齐次递归方程如下：
?
?
?===-+---=7)2(2)1(1)0()
3(3)2(7)1(5)(f f f n f n f n f n f 解 特征方程为：
8
037523=-+-x x x
把特征方程改写成：
036523=-++-x x x x
进行因式分解：
0)12()3(2=+--x x x
最后得：
0)3()1()1(=---x x x
求得特征方程的根为：
31
1
321===q q q
所以，递归方程的通解为：
n
n q c q n c c n f 3
3121)()(++= n c n c c 3321++=
代入初始条件：
1
)0(31=+=c c f
23)1(321=++=c c c f 7
92)2(321=++=c c c f
解此联立方程，得：
11
321=-==c c c
则递归方程的解为：
n
n q c q n c c n f 33121)()(++=
n n -=3
2.3.2 k 阶常系数线性非齐次递归方程
一、k 阶常系数线性非齐次递归方程
1、递归方程的形式：
?
?
?<≤=+-+-+-=k i b i f n g k n f a n f a n f a n f i k 0)()
()()2()1()(21 （2.3.5） 2、通解形式：
)(*)()(n f n f n f +=
其中，)(n f 是对应齐次递归方程的通解，)(*n f 是原非齐次递归方程的特解。
9
3、特解的求取
1）)(n g 是n 的m 次多项式，即
1121)(+-++++=m m m m b n b n b n b n g
（2.3.6）
其中，1,,2,1,+=m i b i 是常数。特解)(*n f 也是n 的m 次多项式：
1121)(*+-++++=m m m m A n A n A n A n f
（2.3.7）
其中，1,,2,1,+=m i A i 为待定系数。
2）)(n g 是如下形式的指数函数：
n m m m m a b n b n b n b n g )()(1121+-++++=
（2.3.8）
其中，a 、1,,2,1,+=m i b i 为常数。
a) a 不是特征方程的重根，特解)(*n f 为：
n m m m m a A n A n A n A n f )()(*1121+-++++= （2.3.9）
其中，1,,2,1,+=m i A i 为待定系数。
b) a 是特征方程的r 重特征根，特解的形式为：
n r m m m m a n A n A n A n A n f )()(*1121+-++++= （2.3.10）
其中，1,,2,1,+=r i A i 是待定系数。
例2.5 二阶常系数线性非齐次递归方程如下：
??
??
?==+---=2)1(1)0(4)2(10)1(7)(2
f f n n f n f n f 解 对应的齐次递归方程的特征方程为：
01072=+-x x
把此方程转换为：
0)5()2(=--x x
得到特征根为：
52
21==q q
所以，对应的齐次递归方程的通解为：
n n c c n f 52)(21+=
令非齐次递归方程的特解为：
3221)(*A n A n A n f ++=
代入原递归方程，得：
23221322132214))2()2((10))1()1((7n A n A n A A n A n A A n A n A =+-+-++-+--++
化简后得到：
10
23212121441333)426(4n A A A n A A n A =+-++-+
由此，得到联立方程：
441=A 042621=+-A A 041333321=+-A A A
解此联立方程，可得：
8
7
122
16
1
321===A A A
所以，非齐次递归方程的通解为：
8
7
1221652)(221++++=n n c c n f n n
把初始条件代入，有：
187
12)0(21=++=c c f
28
3
2052)1(21=++=c c f
解此联立方程，得：
24
191
3
213
21=-=c c 最后，非齐次递归方程的通解为：
8
7
1221652419123213)(2+++?+?-=n n n f n n
例2.6 二阶常系数线性非齐次递归方程如下：
??
??
?==+---=2)1(1)0(2)2(12)1(7)(f f n n f n f n f n
解 对应齐次递归方程的特征方程为：
01272=+-x x
此方程可改写成：
0)4()3(=--x x
所以，方程的解为：
43
21==q q
齐次递归方程的通解为：
n n c c n f 43)(21+=
令非齐次递归方程的特解为：
n A n A n f 2)()(*21+=
11
把特解代入原非齐次递归方程，得：
n n n n n A n A A n A A n A 22))2((122))1((72)(22112121=+-++--+--
整理得：
n A A n A 41022121=-+
可得联立方程：
421=A
010212=-A A
解此联立方程得：
102
21==A A
所以，非齐次递归方程的通解为：
n n n n c c n f 2)102(43)(21+++=
用初始条件代入：
110)0(21=++=c c f 22443)1(21=++=c c f
解此联立方程得：
514
21=-=c c
最后，非齐次递归方程的解为：
n n n n n f 2)102(45314)(++?+?-=
12)5(45314+++?+?-=n n n n
2.4 用递推方法求解递归方程
2.4.1 递推
非齐次递归方程：
?
?
?=+-=c f n g n f b n f )0()
()1()( （2.4.1）
其中，b 、c 是常数，)(n g 是n 的某一个函数。直接把公式应用于式中的)1(-n f ，得到：
)())1()2(()(n g n g n f b b n f +-+-=
)()1()2(2n g n g b n f b +-+-=
)()1())2()3((2n g n g b n g n f b b +-+-+-= )()1()2()3(23n g n g b n g b n f b +-+-+-=
12
=
)()1()2()1()0(21n g n g b n g b g b f b n n +-+-+++=-
∑=-+
=n
i i
n n
i g b
b c 1
)( （2.4.2）
例2.7 汉诺塔问题。
由（2.2.14），汉诺塔的递归方程为：
?
?
?=+-=1)1(1
)1(2)(h n h n h 直接利用（2.4.2）式于汉诺塔的递归方程。此时，
1)(1
2
===n g c b
从n 递推到1，有：
∑-=---+
=1
1
11
)()(n i i
n n i g b
b
c n h
12222221+++++=-- n n
12-=n
2.4.2 用递推法求解变系数递归方程
一、变系数齐次递归方程：
??
?=-=c
f n f n
g n f )0()1()()( （2.4.3）
利用递推方法，容易得到：
)1()1()()(g n g n g c n f -=
（2.4.4）
例2.8 解如下递归函数：
??
?=-=1
)0()
1()(f n f n n f 由（2.4.4）式，容易得到：
1)2()1()( --=n n n n f
!n =
二、变系数非齐次递归方程：
?
?
?=+-=c f n h n f n g n f )0()
()1()()( （2.4.5）
其中，c 是常数，)(n g 和)(n h 是n 的函数。利用（2.4.5）式对)(n f 进行递推，有：
)()1()()(n h n f n g n f +-=
13
)())1()2()1(()(n h n h n f n g n g +-+--= )()1()()2()1()(n h n h n g n f n g n g +-+--= =
+-+-=)1()2()1()()0()1()1()(h g n g n g f g n g n g
)()1()(n h n h n g +-+
+-+-=)
1()
1()1()2()1()()0()1()1()(g h g g n g n g f g n g n g
)
1()2()1()()
()1()2()1()()1()2()1()1()1()2()1()(g g n g n g n h g g n g n g g g n g n h g g n g n g --+---+
???
? ?
?
-+
-=∑
=n
i g i g i g i h f g n g n g 1
)1()1()()()0()1()1()(
（2.4.6）
例2.9 解如下的递归函数：
?
?
?=+-=0)0(!
)1()(f n n f n n f 对方程进行递推，有：
!)!)1()2()1(()(n n n f n n n f +-+--=
!2)2()1(n n f n n +--= =
!)0(!n n f n += !n n =
如果直接使用公式（2.4.6），此时，!)(,)(n n h n n g ==，有：
0)0(1
)1(!
1
)1()(1
=--=∑
=f i i i n n n f n
i
!n n =
得到同样结果。
例2.10 解如下的递归方程
?
?
?=+-=0)0()1(2)(f n
n f n f 解 对方程进行递推，有：
n n n f n f +-+-=))1()2(2(2)(
n n n f +-+-=)1(2)2(22
=
14
n f n n n 0212222)0(2+++=--
)(21
i n n i i -=
∑-=
∑=-?=
n
i i
n i 12
∑==n
i i
n
i
1
2
2
由公式（2.1.24），得
222222)(1--=??? ?
?
+-=+n n n f n n n
如果直接使用公式（2.4.6），此时，n n h n g ==)(,2)(，同样有：
∑==n
i i
n
i
n f 1
2
2
)(221--=+n n
2.4.3 换名
例2.11 解如下的递归方程：
?
?
?=-+=1)1(1
2/)2/(2)(f n n f n f 其中， k n 2=。
解 把n 表示成k 的关系，原递归方程改写为：
??
???=-+=--1)2(1
2)2(2)2(0
11f f f k k k 再令：
)()2()(n f f k g k ==
于是，原递归方程可写为：
??
??
?=-+-=-1)0(1
2)1(2)(1g k g k g k 对上面方程进行递推，有：
12)12)2(2(2)(22-+-+-=--k k k g k g
15
1222)2(212--?+-=-k k g 12223)3(2213---?+-=-k k g
=
∑-=--
?+=1
1
2
2
)0(2k i i
k k k g
)221(21
∑
-=--+=k i k i k
k
)21
2
1(21
∑=-
+=k
i i
k
k
))2
11(21(2k k k --+= )212(2k
k k += 122
1+=k k
1log 2
1
+=
n n 如果直接使用（2.4.6）式，可得：
)2121(2)()(1
1∑
=--+
==k
i i
i k
k g n f
))2121(
1(21
∑
=-+
=k
i i
k
)212(2k
k k += 1log 2
1
+=
n n 结果一样。
例2.12 解如下的递归方程：
??
?=+=c
f n
b n f n f )1()2/(2)( 其中，b 、
c 为常数，k n 2=。
解 把n 表示成k 的关系，原递归方程改写为：
16
??
???=+=-1)2(2)2(2)2(0
1f b f f k
k k 再令：
)()2()(n f f k g k ==
于是，原递归方程可写为：
??
??
?=+-=c g b k g k g k
)0(2)1(2)( 直接使用（2.4.6）式，可得：
)22(2)()(1
∑
=+
==k
i i
i k
b c k g n f
)(21
∑=+
=k
i k
b c
)(2k b c k +=
n c n n b +=log
利用递归思想解决计数问题 福建省永定第一中学 简绍煌 我们常会遇到一些看似排列组合应用题的计数问题，但其复杂的情形有时令人无从下手，若是利用递归思想建立递归方程加以求解，则往往能够迎刃而解． 【例1】有一楼梯共10级，如果规定每步只能跨上一级或二级，要上10级，共有多少种走法？ 解 设上n 级楼梯共有n a 种走法，当1n =时，11a =；当2n =时，22a =． 当有(2)n n >级楼梯时，其走法分两类． 第一类：走完前面1n -级楼梯有1n a -种走法，走第n 级只有1种走法； 第二类：走完前面2n -级楼梯有2n a -种走法，走第1n -级与第n 级楼梯时一步走，也是1种走法． 由分类计数原理，知n 级楼梯的走法为21(2)n n n a a a n N n --=+∈>且，． 由此可以算出1089a =． 点评 其通项公式可用换元法转化为一阶线性递归数列求解． 令11n n n c a x a +=-，使数列{}n c 是以2x 为公比的等比数列(12x x 、待定)． 即211211()n n n n a x a x a x a +++-=-，∴212112()n n n a x x a x x a ++=+-．对照已给递归式， 有12121 1x x x x +==-，，即12x x 、是方程210x x --=的两个根． 从而121211112222x x x x += === ∴211111(222n n n n a a a a +++-=-) ① 或211111(222n n n n a a a +++-=-) ② 由式①得1 1131(222n n n a a -++-=； 由式②得1 1131(222 n n n a a -++--=． 消去 1n a +，得11n n n a --? =?? ． 【例2】将数字123n ，，，，填入标号为123n ，，，，的n 个方格内，每格一个数字，则 标号与所填数字均不同的填法共有多少种？ 解 设这n 个自然数的错排数为n a ． 当1n =时，10a =；当2n =时，21a =． 当3n ≥时，n 个自然数的错排数可以分两类情况计算． 第一类：自然数(11)k k n ≤≤-与n 互换，这时错排数为2n a -； 第二类：自然数n 在第k 位上，但自然数不在第n 位上．这时就把第n 位看做第k 位，相当于将n 以外的1n -个自然数进行错排，错排数为1n a -． 所以，自然数n 在第k 位上的错排数共有21n n a a --+种，由于k 可以是121n - ，，，共 1n -种可能，故n 个自然数的错排数为21(1)()(3)n n n a n a a n --=-+≥．① 由①式得，112[(1)]n n n n a a a n a ----=---，∴112 (1)[]!!!! n n n n a na a n a n n n n -----=--，
递归方程解的渐近阶的求法 递归算法在最坏情况下的时间复杂性渐近阶的分析，都转化为求相应的一个递归方程的解的渐近阶。因此，求递归方程的解的渐近阶是对递归算法进行分析的关键步骤。 递归方程的形式多种多样，求其解的渐近阶的方法也多种多样。这里只介绍比较实用的五种方法。 1.代入法这个方法的基本步骤是先推测递归方程的显式解，然后用数学归纳法证明这 一推测的正确性。那么，显式解的渐近阶即为所求。 2.迭代法这个方法的基本步骤是通过反复迭代，将递归方程的右端变换成一个级数， 然后求级数的和，再估计和的渐近阶；或者，不求级数的和而直接估计级数的渐近阶，从而达到对递归方程解的渐近阶的估计。 3.套用公式法这个方法针对形如：T (n)=aT (n / b)+f (n) 的递归方程，给出三种情况 下方程解的渐近阶的三个相应估计公式供套用。 4.差分方程法有些递归方程可以看成一个差分方程，因而可以用解差分方程(初值问 题)的方法来解递归方程。然后对得到的解作渐近阶的估计。 5.母函数法这是一个有广泛适用性的方法。它不仅可以用来求解线性常系数高阶齐次 和非齐次的递归方程，而且可以用来求解线性变系数高阶齐次和非齐次的递归方程，甚至可以用来求解非线性递归方程。方法的基本思想是设定递归方程解的母函数，努力建立一个关于母函数的可解方程，将其解出，然后返回递归方程的解。 本章将逐一地介绍上述五种方法，并分别举例加以说明。 本来，递归方程都带有初始条件，为了简明起见，我们在下面的讨论中略去这些初始条件。 递归方程组解的渐进阶的求法——代入法 用这个办法既可估计上界也可估计下界。如前面所指出，方法的关键步骤在于预先对解答作出推测，然后用数学归纳法证明推测的正确性。 例如，我们要估计T(n)的上界，T(n)满足递归方程： 其中是地板(floors)函数的记号，表示不大于n的最大整数。 我们推测T(n)=O(n log n)，即推测存在正的常数C和自然数n0，使得当n≥n0 时有：
特征方程特征根法求解数列通项公式 一：A(n+1)=pAn+q, p,q为常数. （1）通常设：A(n+1)-λ＝p(An-λ), 则λ=q／(1-p). （2）此处如果用特征根法： 特征方程为：x=px+q，其根为x=q/（1-p） 注意：若用特征根法，λ的系数要是-1 例一：A（n+1)=2An+1 , 其中q=2,p=1,则 λ=1/（1-2）= -1那么 A（n+1）+1=2（An+1） 二：再来个有点意思的,三项之间的关系： A(n+2)=pA(n+1)+qAn，p,q为常数 （1）通常设：A(n+2)-mA(n+1)=k[pA(n+1)-mAn], 则m+k=p, mk=q （2）此处如果用特征根法： 特征方程是y×y=py+q（※） 注意： ①m n为（※）两根。 ②m n可以交换位置，但其结果或出现两种截然不同的数列形式，但同样都可以计算An，而且还会有意想不到的惊喜， ③m n交换位置后可以分别构造出两组An和A(n+1)的递推公式，这个时侯你会发现，这是一个关于An和A(n+1)的二元一次方程组，那么不就可以消去A（n+1），留下An，得了，An求出来了。 例二：A1=1,A2=1,A(n+2)= - 5A（n+1）+6An， 特征方程为：y×y= - 5y+6 那么，m=3,n=2,或者m=2，n=3 于是，A（n+2）-3A（n+1）=2[A（n+1）-3A] (1) A（n+2）-2A（n+1）=3[A（n+1）-2A] (2) 所以，A（n+1）-3A（n）= - 2 ^ n (3) A（n+1）-2A（n）= - 3 ^ (n-1) (4) you see 消元消去A（n+1），就是An勒 例三： 【斐波那挈数列通项公式的推导】斐波那契数列：0，1，1，2，3，5，8，13，21…… 如果设F(n)为该数列的第n项(n∈N+)。那么这句话可以写成如下形式： F(0) = 0，F(1)=F(2)=1,F(n)=F(n-1)+F(n-2) (n≥3) 显然这是一个线性递推数列。 通项公式的推导方法一：利用特征方程 线性递推数列的特征方程为： X^2=X+1 解得 X1=(1+√5)/2, X2=(1-√5)/2. 则F(n)=C1*X1^n + C2*X2^n ∵F(1)=F(2)=1 ∴C1*X1 + C2*X2 C1*X1^2 + C2*X2^2
递归方程求解方法综述 摘要：随着计算机科学的逐步发展，各种各样的算法相继出现，我们需要对算法进行分析，以选择性能更好的解决方案。算法分析中计算复杂度常用递归方程来表达，因此递归方程的求解有助于分析算法设计的好坏。阐述了常用的3种求解递归方程的方法：递推法、特征方程法和生成函数法。这3种方法基本上可以解决一般规模递归方程的求解问题。 关键词：递归；递推法；特征方程；生成函数 0引言 寻求好的解决方案是算法分析的主要目的，问题的解决方案可能不只一个，好的方案应该执行时间最短，同时占有存储空间最小，故算法分析一般考虑时间复杂性、空间复杂性两方面的参数。在算法分析时我们采用时间耗费函数来表示时间参数，用当问题规模充分大时的时间耗费函数的极限表示时间复杂度。 一般算法对应的时间耗费函数常用递归方程表示，找出递归方程的解，就可以表示其对应算法复杂度的渐进阶，从而比较算法的优劣。因此研究递归方程的解法意义重大。下文将分析并给出常用递归方程的3种解法。 1递归方程的解法 递归方程是对实际问题求解的一种数学抽象,递归的本质在于将原始问题逐步划分成具有相同解题规律的子问题来解决,原始问题与子问题仅在规模上有大小区别,并且子问题的规模比原始问题的
规模要小。对于规模为n的原始问题,我们通常会寻找规模n的问题与规模n-1或者规模n/2的问题之间存在的联系,从而进一步推导出具有递归特性的运算模型。 根据递归方程的一般形式，常用的解法有三种，分别是递推法、公式法及生成函数法。下面就分别来分析其求解过程。 1.1递推法 当递归方程形式简单且阶数较低时，一般可以采用递推法求解，根据一步一步递推找到方程的递推规律，得到方程的解。下面举例说明： t(1)=0 t(n)=2t(n/2)+n2(n≥2) t(n)=2t(n/2)+n2=2(2t(n/22)+(n/2)2)+n2 =22t(n/2)2+2n2/22+n2 =22(2t(n/23)+(n/22)2)+2n2/22+n2 =23(2t(n/23)+22n2/(22)2)+2n2/(22)1+n2… =2kt(n/2k)+∑k-1i=02in2(22)i递推到这里我们就可以发现递 归规律，找到递归出口， t(1)=0，令n=2k 则可以得到如下结果：t(n) =2kt(1) +∑k-1i=0n2(1/2)i)= n2(1-(1/2)k1-1/2)=2n2-2n 上面得到方程的解，我们来分析其对应算法复杂性的渐进阶，根据渐进阶定理有：设有函数f(n)，g(n）均是规模n的函数，则o(f(n))+o(g(n))=o(max(f(n), g(n)))。故有t(n)=o(n2)。 1.2公式法
特征方程法求解递推关系中的数列通项 考虑一个简单的线性递推问题. 设已知数列}{n a 的项满足 其中,1,0≠≠c c 求这个数列的通项公式. 采用数学归纳法可以求解这一问题，然而这样做太过繁琐，而且在猜想通项公式中容易出错，本文提出一种易于被学生掌握的解法——特征方程法：针对问题中的递推关系式作出一个方程,d cx x +=称之为特征方程；借助这个特征方程的根快速求解通项公式.下面以定理形式进行阐述. 定理1.设上述递推关系式的特征方程的根为0x ，则当10a x =时，n a 为常数列，即0101,;x b a a x a a n n n +===时当， 其中}{n b 是以c 为公比的等比数列，即01111,x a b c b b n n -==-. 证明：因为,1,0≠c 由特征方程得.10c d x -=作换元,0x a b n n -= 则.)(110011 n n n n n n cb x a c c cd ca c d d ca x a b =-=--=--+=-=-- 当10a x ≠时，01≠b ，数列}{n b 是以c 为公比的等比数列，故;11-=n n c b b 当10a x =时，01=b ，}{n b 为0数列，故.N ,1∈=n a a n （证毕） 下面列举两例，说明定理1的应用. 例1．已知数列}{n a 满足：,4,N ,23 111=∈--=+a n a a n n 求.n a 解：作方程.2 3,23 10-=--=x x x 则 当41=a 时，.2112 3 ,1101= +=≠a b x a 数列}{n b 是以3 1 -为公比的等比数列.于是.N ,)3 1 (2112323,)31(211)3 1 (111 1∈-+-=+-=-=-=---n b a b b n n n n n n 例2．已知数列}{n a 满足递推关系：,N ,)32(1∈+=+n i a a n n 其中i 为虚数单位. 当1a 取何值时，数列}{n a 是常数数列？ 解：作方程,)32(i x x +=则.5 360i x +-= a 1= b a n+1=ca n +d
第四章 方程求解 1 代数方程(组)求解 1.1 常用求解工具—solve 求解代数方程或代数方程组, 使用Maple 中的solve 函数. 求解关于x 的方程eqn=0的命令格式为： solve(eqn, x); 求解关于变量组vars 的方程组eqns 的命令为： solve(eqns, vars); > eqn:=(x^2+x+2)*(x-1); := eqn () + + x 2x 2() ? x 1 > solve(eqn,x); ,,1? + 1212I 7? ? 1212 I 7 当然, solve 也可以求解含有未知参数的方程： > eqn:=2*x^2-5*a*x=1; := eqn = ? 2x 25a x 1 > solve(eqn,x); , + 54a 14 + 25a 28 ? 54a 14 + 25a 28 solve 函数的第一个参数是有待求解的方程或方程的集合, 当然也可以是单个表达式或者表达式的集合, 如下例： > solve(a+ln(x-3)-ln(x),x); 3e a ? + 1e a 对于第二个参数, Maple 的标准形式是未知变量或者变量集合, 当其被省略时, 函数indets 自动获取未知变量. 但当方程中含有参数时, 则会出现一些意想不到的情况： > solve(a+ln(x-3)-ln(x));
{}, = x x = a ? + ()ln ? x 3()ln x 很多情况下, 我们知道一类方程或方程组有解, 但却没有解决这类方程的一般解法, 或者说没有解析解. 比如, 一般的五次或五次以上的多项式, 其解不能写成解析表达式. Maple 具备用所有一般算法尝试所遇到的问题, 在找不到解的时候, Maple 会用RootOf 给出形式解. > x^7-2*x^6-4*x^5-x^3+x^2+6*x+4; ? ? ? + + + x 72x 64x 5x 3x 26x 4 > solve(%); + 15 ? 15()RootOf , ? ? _Z 5_Z 1 = index 1()RootOf , ? ? _Z 5_Z 1 = index 2(RootOf ,) ? ? _Z 5_Z 1 = index 3,,,,()RootOf , ? ? _Z 5_Z 1 = index 4()RootOf , ? ? _Z 5_Z 1 = index 5,, > solve(cos(x)=x,x); ()RootOf ? _Z ()cos _Z 对于方程组解的个数可用nops 命令获得, 如： > eqns:={seq(x[i]^2=x[i],i=1..7)}; := eqns {,,,,,, = x 12x 1 = x 22x 2 = x 32x 3 = x 42x 4 = x 52x 5 = x 62x 6 = x 72 x 7} > nops({solve(eqns)});128 但是, 有时候, Maple 甚至对一些“显而易见”的结果置之不理, 如： > solve(sin(x)=3*x/Pi,x); ()RootOf ? 3_Z ()sin _Z π 此方程的解为0 ,6π ±, 但Maple 却对这个超越方程无能为力, 即便使用allvalues 求解也只有下述结果： > allvalues(%); ()RootOf , ? 3_Z ()sin _Z π0. 另外一个问题是, Maple 在求解方程之前,会对所有的方程或表达式进行化简, 而不管表达式的类型, 由此而产生一些低级的错误： > (x-1)^2/(x^2-1); () ? x 12 ? x 21 > solve(%); 1
特征方程法求解递推关系中的数列通项 一、（一阶线性递推式）设已知数列}{n a 的项满足d ca a b a n n +==+11,,其中,1,0≠≠c c 求这个数列的通项公式。 采用数学归纳法可以求解这一问题，然而这样做太过繁琐，而且在猜想通项公式中容易出错，本文提出一种易于被学生掌握的解法——特征方程法：针对问题中的递推关系式作出一个方程,d cx x +=称之为特征方程；借助这个特征方程的根快速求解通项公式.下面以定理形式进行阐述. 定理1：设上述递推关系式的特征方程的根为0x ，则当10a x =时，n a 为常数列，即0101,;x b a a x a a n n n +===时当，其中}{n b 是以c 为公比的等比数列，即01111,x a b c b b n n -==-. 证明：因为,1,0≠c 由特征方程得.10c d x -= 作换元,0x a b n n -=则.)(110011 n n n n n n cb x a c c cd ca c d d ca x a b =-=--=--+=-=-- 当10a x ≠时，01≠b ，数列}{n b 是以c 为公比的等比数列，故;11-=n n c b b 当10a x =时，01=b ，}{n b 为0数列，故.N ,1∈=n a a n （证毕） 下面列举两例，说明定理1的应用. 例1．已知数列}{n a 满足：,4,N ,23 1 11=∈--=+a n a a n n 求.n a 解：作方程.2 3 ,2310-=--=x x x 则 当41=a 时，.211 23,1101=+=≠a b x a 数列}{n b 是以3 1 -为公比的等比数列.于是 .N ,)3 1 (2112323,)31(211)31(1111∈-+-=+-=-=-=---n b a b b n n n n n n 例2．已知数列}{n a 满足递推关系：,N ,)32(1∈+=+n i a a n n 其中i 为虚数
特征根法求解二阶常系数线性微分方程 关于二阶常系数线性微分方程的解法： 1．线性齐次方程0=+'+''cy y b y a 的通解 解法 先解特征方程02=++c br ar 的根．设特征根为a ac b b r 2422 ,1-±-=，分以下三种情况： （1） 当042>-ac b 时，特征方程有两个相异的实根() ac b b a r 42122,1-±-=，则方程的通解为 x r x r C C y 21e e 21+=． （2）当042=-ac b 时，特征方程有重根a b r 2-=，则方程的通解为 ()x r x C C y e 21+=． （3）当042 <-ac b 时，特征方程有一对共轭的复根 a b ac a b r 2i 42i 22,1?-±- =±=βα， 则方程的通解为 ()x C x C y x ββαsin cos e 21+=． 定理 若21,y y 为齐次方程0=+'+''cy y b y a 的两个解，则 2211y C y C y += 亦是齐次方程的解，其中21,C C 是任意常数．又若21,y y 为线性无关时，则2211y C y C y +=是齐次方程的通解． 2．线性非齐次方程)(x f cy y b y a =+'+''的通解 定理 设* y 是非齐次线性方程的一个特解，而y 是相应的线性齐次方程的通解，则其和 *y y y += 为线性非齐次方程的通解． 具体解法： （1）先求)(x f cy y b y a =+'+''的特解*y （2）再求对应线性齐次方程的通解y ，根据定理相加即可* y y y +=
例题1用特征根法求微分方程044=+'+''y y y 的通解 解：特征方程为r 2+4r+4=0 所以，（r+2）2=0 得重根r 1=r 2=-2，所以，方程的一般解为y=(c 1+c 2x)e -2x 例题2用特征根法求微分方程y``+3y`+2y=0的一般解 解：特征方程的解r 1=-1，r 2=-2一般解 x x e C e C y --+=221 例题3 用特征根法求微分方程02520422=+-x dt dx dt x d ;的一般解 解 微分方程的特征方程为 4r 2-20r +25=0, 即(2x -5)2=0, 其根为2 521==r r , 故微分方程的通解为 t t xe C e C x 252251+=, 即t e t C C x 2521)(+= 例题4求下列微分方程满足所给初始条件的特解y ''-3y '-4y =0, y |x =0=0, y '|x =0=-5; 解：微分方程的特征方程为 r 2 -3r -4=0, 即(r -4)(r +1)=0, 其根为r 1=-1, r 2=4, 故微分方程的通解为 y =C 1e -x +C 2e 4x . 由y |x =0=0, y '|x =0=-5, 得 ???-=+-=+54021 21C C C C , 解之得C 1=1, C 2=-1. 因此所求特解为 y =e -x -e 4x . 例题5求微分方程的通解2y ''+y '-y =2e x 解 微分方程的特征方程为 2r 2+r -1=0, 其根为211= r , r 2=-1, 故对应的齐次方程的通解为 x x e C e C Y -+=2211. 因为f (x )=2e x , λ=1不是特征方程的根, 故原方程的特解设为 y *=Ae x , 代入原方程得
当一个算法(如二分查找)中包含对自己的递归调用时，关于这个算法时间复杂性的分析最终都转化为一个递归方程的求解问题，而这样的算法不在少数。实际上这是数学领域的问题，但是计算机科学又怎么能脱离数学而存在呢？^_^ 数学是好东西呀，可惜自己在这方面造诣颇浅，今生之遗憾亚。^_^ 还好，解决递归方程涉及的数学知识我还是能应付的了的^_^。在MIT算法导论中介绍了3种方法，我们这里就说说这三种方法！这些是基础，如果以后要深入研究算法的话，这些知识是必须要精通的；如果并不想在算法方面有所深入的话，多学些知识也没错。我本身也是在学习，像这类的知识一般都比较死性，有些记住了，就可以掌握了。 1、Substitution Method 这是一种使用数学归纳法推导证明的方法，其步骤为先假设一个解，然后带入到递归方程中，利用数学归纳法推导，以验证假设的解是否合理。我们拿ITA(Introduction to Algorithm)中的例子说明吧，比较保险^_^。 [Ex1.] T(n) = 4T(n/2) + n，解这个递归等式，分析T(n)的渐近性。 解：(这里我们只来找上界) 我们假设T(1) = θ(1)，猜测一个解T(n) = O(n^3)，根据O符号的定义，我们得到对k < n, 有T(k) <= ck^3，把这个解代入到T(n) = 4T(n/2) + n，并进行推导得出： T(n) = 4T(n/2) + n <= 4c((n/2)^3) + n = (c/2)n^3 + n = cn^3 - ((c/2)n^3 - n) 当c >= 2, n >= 1时，((c/2)n^3 - n) >= 0，这时T(n) <= cn^3，即T(n) = O(n^3)； 我们再回过头来看看当n = 1时这个解是否成立，即证明一下T(1) = θ(1)。对于1 <= n < n0, θ(1) <= cn^3 (c足够大)，即该推导出的解也满足初始条件，所以O(n^3)是T(n)的一个上界。但是O(n^3)是否是严紧的上界呢，我们不妨缩小上界范围再推导一次，这次我们猜测解为T(n) = O(n^2)，根据O符号的定义，我们得到对k < n, 有T(k) <= ck^2，把这个解代入到T(n) = 4T(n/2) + n，并进行推导得出： T(n) = 4T(n/2) + n <= 4c((n/2)^2) + n = cn^2 + n = cn^2 - (-n) 不能严格符合T(n) <= cn^2的定义，所以推导失败。但是失败是不是说明，T(n) = O(n^2)一定不成立呢？我们再做一次最后的努力，当出现上面的这种情况时，我们假设解仍为：T(n) = O(n^2)，只是我们选择对k < n, 有T(k) <= ak^2 - bk，我们选择减去一个低阶的项，这不会影响到n足够大时的渐进性的，这里是一个常用的技巧。 T(n) = 4T(n/2) + n <= 4(a(n/2)^2 - b(n/2)) + n = an^2 - bn - (bn - n) <= an^2 - bn (当b >= 1时) 这样我们找到了严紧解T(n) = O(n^2)。
附：递归关系求解 江超群 2016.10 代入法 例：求解递归关系 a n =a n?1+n ?1,a 1=0 应用：求一个递归关系为T (n )=T (n ?1)+简单表达式 类问题的时间复杂度 特征方程法 齐次递推关系方程求解 递归方程T (n )=r 1T (n ?1)+r 2T (n ?2)+?+r k T (n ?k ) 它对应的齐次关系的特征方程：x k =r 1x k?1+r 2x k?2+?+r k 特别的：二阶齐次方程求解 递归方程为：T (n )=r 1T (n ?1)+r 2T (n ?2) 它的递归方程为x 2?r 1x ?r 2=0 求解： 如果特征方程有两个不同实根x 1,x 2 ，则T (n )的通解是T (n )=u 1x 1n +u 2x 2n ，根据初值条件确定u 1,u 2后，得到方程的特解。 如果特征方程有一个根x 0，则T (n )的通解是T (n )=u 1x 0n +nu 2x 0n ，根据初值条件确定u 1,u 2得到方程的特解。 非齐次递推关系方程求解 非齐次特征方程解的形式为T (n )=r 1T (n ?1)+r 2T (n ?2)+?+r k T (n ?k )+f (n ) ()()()()()()123111 (2)1 ((3)2)2 ((...()...3)2)1.(1...321) 1,1211,0212n n n n n k n k n k a a n a n n a n n n a n k n n n a k n k k k k a kn k n n n a n n a n n ------=+-=+-+-=+-+-+-=+-++-+-+-=+-+-+++++=+-=--=+--=- =令，
目录 递归方程组解的渐进阶的求法——代入法 (11) 递归方程组解的渐进阶的求法——迭代法 (14) 递归方程组解的渐进阶的求法——套用公式法 (17) 递归方程组解的渐进阶的求法——差分方程法 (3) 递归方程组解的渐进阶的求法——母函数法 (7) 递归方程解的渐近阶的求法 递归方程组解的渐进阶的求法——套用公式法 这个方法为估计形如： T(n)=aT(n/b)+f(n) (6.17) 的递归方程解的渐近阶提供三个可套用的公式。(6.17)中的a≥1和b≥1是常数，f (n)是一个确定的正函数。 (6.17)是一类分治法的时间复杂性所满足的递归关系，即一个规模为n的问题被分成规模均为n/b的a个子间题，递归地求解这a个子问题，然后通过对这a个子间题的解的综合，得到原问题的解。如果用T(n)表示规模为n的原问题的复杂性，用f(n)表示把原问题分成a个子问题和将a个子问题的解综合为原问题的解所需要的时间，我们便有方程(6.17)。 这个方法依据的是如下的定理：设a≥1和b≥1是常数f (n)是定义在非负整数上的一个确定的非负函数。又设T(n)也是定义在非负整数上的一个非负函数，且满足递归方程(6.17)。方程(6.17)中的n/b可以是[n/b]，也可以是n/b。那么，在f(n)的三类情况下，我们有T(n)的渐近估计式： 1. 若对于某常数ε>0，有 ， 则 ； 2. 若 ， 则 ；
3. 若对其常数ε>0，有 且对于某常数c>1和所有充分大的正整数n有af(n/b)≤cf(n)，则T(n)=θ(f(n))。 这里省略定理的证明。 在应用这个定理到一些实例之前，让我们先指出定理的直观含义，以帮助读者理解这个定理。读者可能已经注意到，这里涉及的三类情况，都是拿f(n)与作比较。定理直观地告诉我们，递归方程解的渐近阶由这两个函数中的较大者决定。在第一类情况下，函数较大，则T(n)=θ()；在第三类情况下，函数f(n)较大，则T(n)=θ(f (n))；在第二类情况下，两个函数一样大，则T(n)=θ()，即以n的对数作为因子乘上f(n)与T(n)的同阶。 此外，定理中的一些细节不能忽视。在第一类情况下f(n)不仅必须比小，而且必须是多项式地比小，即f(n)必须渐近地小于与的积，ε是一个正的常 数；在第三类情况下f(n)不仅必须比大，而且必须是多项式地比大，还要满足附加的“正规性”条件：af(n/b)≤cf(n)。这个附加的“正规性”条件的直观含义是a个子间题的再分解和再综合所需要的时间最多与原问题的分解和综合所需要的时间同阶。我们在一般情况下将碰到的以多项式为界的函数基本上都满足这个正规性条件。 还有一点很重要，即要认识到上述三类情况并没有覆盖所有可能的f(n)。在第一类情况和第二类情况之间有一个间隙：f(n)小于但不是多项式地小于；类似地，在第二类情况和第三类情况之间也有一个间隙：f(n)大于但不是多项式地大于。如果函数f(n)落 在这两个间隙之一中，或者虽有，但正规性条件不满足，那么，本定理无能为力。 下面是几个应用例子。 例1考虑 T(n)=9T(n/3)+n0
特征方程法求解递推关系中的数列通项 湖北省竹溪县第一高级中学徐鸿 考虑一个简单的线性递推问题. 设已知数列的项满足 其中求这个数列的通项公式. 采用数学归纳法可以求解这一问题，然而这样做太过繁琐，而且在猜想通项公式中容易出错，本文提出一种易于被学生掌握的解法——特征方程法：针对问题中的递推关系式作出一个方程称之为特征方程；借助这个特征方程的根快速求解通项公式.下面以定理形式进行阐述. 定理1设上述递推关系式的特征方程的根为，则当时，为常数列，即 ，其中是以为公比的等比数列，即. 证明：因为由特征方程得作换元 则 当时，，数列是以为公比的等比数列，故 当时，，为0数列，故（证毕） 下面列举两例，说明定理1的应用. 例1已知数列满足：求 解：作方程 当时，数列是以为公比的等比数列.于是 例2已知数列满足递推关系：其中为虚数单位. 当取何值时，数列是常数数列？
解：作方程则 要使为常数，即则必须 现在考虑一个分式递推问题（*）. 例3已知数列满足性质：对于且求的通项公式. 将这问题一般化，应用特征方程法求解，有下述结果. 定理2如果数列满足下列条件：已知的值且对于，都有（其中p、q、r、h均为常数，且），那么，可作特征方程. （1）当特征方程有两个相同的根（称作特征根）时， 若则 若，则其中特别地，当存在使 时，无穷数列不存在. （2）当特征方程有两个相异的根、（称作特征根）时，则，其中 证明：先证明定理的第（1）部分. 作交换 则 ① ∵是特征方程的根，∴
将该式代入①式得② 将代入特征方程可整理得这与已知条件矛盾.故特征方程的根于是 ③ 当，即=时，由②式得故 当即时，由②、③两式可得此时可对②式作如下变化： ④ 由是方程的两个相同的根可以求得 ∴ 将此式代入④式得 令则故数列是以为公差的等差数列. ∴ 其中 当时， 当存在使时，无意义.故此时，无穷数列是不存在的. 再证明定理的第（2）部分如下： ∵特征方程有两个相异的根、，∴其中必有一个特征根不等于，不妨令于是可作变换 故，将代入再整理得
特征方程法求解递推关系中的数列通项（二） 三、(分式递推式)定理3：如果数列}{n a 满足下列条件：已知1a 的值且对于N ∈n ，都有h ra q pa a n n n ++=+1（其中p 、q 、r 、h 均为常数，且r h a r qr ph -≠≠≠1,0,），那么，可作特征方程h rx q px x ++=. （1）当特征方程有两个相同的根λ（称作特征根）时， 若,1λ=a 则;N ,∈=n a n λ 若λ≠1a ，则,N ,1∈+=n b a n n λ其中.N ,)1(11∈--+-=n r p r n a b n λλ特别地，当存在,N 0∈n 使00=n b 时，无穷数列}{n a 不存在. （2）当特征方程有两个相异的根1λ、2λ（称作特征根）时，则11 2--=n n n c c a λλ，,N ∈n 其中).(,N ,)(211212111λλλλλ≠∈----= -a n r p r p a a c n n 其中 例3、已知数列}{n a 满足性质：对于,324,N 1++= ∈-n n n a a a n 且,31=a 求}{n a 的通项公式. 解:依定理作特征方程,3 24++=x x x 变形得,04222=-+x x 其根为.2,121-==λλ故特征方程有两个相异的根，使用定理2的第（2）部分，则有 .N ,)2 21211(2313)(11212111∈?-?-?+-=--?--=--n r p r p a a c n n n λλλλ ∴.N ,)5 1(521∈-= -n c n n ∴.N ,1)51(521)51(52211112∈----?-=--=--n c c a n n n n n λλ 即.N ,) 5(24)5(∈-+--=n a n n n
递归数列通项公式的求法 确定数列的通项公式，对于研究数列的性质起着至关重要的作用。求递归数列的通项 公式是解决数学竞赛中有关数列问题的关键，本文着重对递归数列通项公式加以研究。 基础知识 定义：对于任意的* N n ∈，由递推关系),,,(21k n n n n a a a f a ---= 确定的关系称为k 阶递归关系或称为k 阶递归方程，由k 阶递归关系及给定的前k 项k a a a ,,,21 的值(称为初始值)所确定的数列称为k 阶递归数列。若f 是线性的，则称为线性递归数列，否则称为非线性递归数列，在数学竞赛中的数列问题常常是非线性递归数列问题。 求递归数列的常用方法： 一．公式法 (1)设}{n a 是等差数列，首项为1a ，公差为d ，则其通项为d m n a a m n )(-+=； (2)设}{n a 是等比数列，首项为1a ，公比为q ，则其通项为m n m n q a a -=； (3)已知数列的前n 项和为n S ，则) 2() 1(11 ≥=??? -=-n n S S S a n n n 。 二．迭代法 迭代恒等式：112211)()()(a a a a a a a a n n n n n +-++-+-=--- ； 迭乘恒等式： 11 2211a a a a a a a a n n n n n ????= --- ，(0≠n a ) 迭代法能够解决以下类型一和类型二所给出的递推数列的通项问题： 类型一：已知)(,11n f a a b a n n +==+，求通项n a ； 类型二：已知n n a n f a b a )(,11==+，求通项n a ； 三．待定系数法 类型三：已知)1(,11≠+==+p q pa a b a n n ，求通项n a ； 四．特征根法 类型四：设二阶常系数线性齐次递推式为n n n qx px x +=++12（0,,1≠≥，q q p n 为常数），其特征方程为q px x +=2 ，其根为特征根。 （1）若特征方程有两个不相等的实根βα,，则其通项公式为n n n B A x βα+=（1≥n ），其中A 、B 由初始值确定； （2）若特征方程有两个相等的实根α，则其通项公式为1 )1([--+=n n n B A x αα（1≥n ）， 其中A 、B 由初始值确定。
解递归方程 下面的求解方法，其正确性可阅读组合数学中的相关内容。 1、 递推法 例：Hanoi 塔问题递归算法的时间复杂性，由以下递归方程给出： ()2(1) 1 2(1)1T n T n n T =-+≥??=? 递推求解如下： 232122122()2(1)1 2(2(2)1)1 2(2)21 2(3)221 ...... 2(1)2 (221) 22 (221) 21 n n n n n T n T n T n T n T n T ----=-+=-++=-++=-++++=+++++=+++++=- 所以，Hanoi 塔问题递归算法的时间复杂性为：()(2)n T n O = 例：分治法实例。设n 表示问题的尺寸，n/b 表示将问题分成a 个子问题后的每个子问题的尺寸，其中a,b 为常数。d(n)表示在分解或合成子问题而得到整个问题解决时的时间耗费。则整个问题的时间耗费由下面的递归方程给出： ()(/)() 2(1)1T n aT n b d n n T =+≥??=? 递推求解如下： 22223233221 0()((/)(/))() (/)(/)() ((/)(/))(/)() (/)(/)(/)() ...... (/)(/)k k k i i i T n a aT n b d n b d n a T n b ad n b d n a aT n b d n b ad n b d n a T n b a d n b ad n b d n a T n b a d n b -==++=++=+++=+++=+∑ 设：k n b =，则log b k n =，有： 1 0()(1)(/)k k i i i T n a T a d n b -==+∑ 当()d n 为常数时，有：
用特征方程与特征根解数列线性递推关系式的通项公式 一.特征方程类型与解题方法 类型一 递推公式为An+2＝aAn+1＋bAn 特征方程为 X 2 =aX+b 解得两根X 1 X 2 (1)若 X 1≠X 2 则A n =pX 1n +qX 2 n (2)若X 1=X 2=X 则A n =(pn+q)X n (其中p.q 为待定系数，由A 1.A 2联立方程求得) (3)若为虚数根，则为周期数列 类型二 递推公式为 特征方程为X = d c b a X X ++ 解得两根X 1 X 2 (1)若X 1≠X 2 则计算2111x A x A n n --++=2 1 x d cA b aA x d cA b aA n n n n -++-++=k 2 1x A x A n n -- 接着做代换B n =2 1 x A x A n n -- 即成等比数列 （2）若X 1=X 2=X 则计算x A n -+11=x d cA b aA n n -++1 =k+x A n -1 接着做代换B n =x A n -1 即成等差数列 (3)若为虚数根，则为周期数列 类型三 递推公式为 特征方程为X =d c b ax X ++2 解得两根X 1 X 2 。然后参照类型二的方法进行整理 类型四 k 阶常系数齐次线性递归式 A n+k =c 1A n+k-1+c 2A n+k-2+…+c k A n 特征方程为 X k = c 1X k-1+c 2X k-2+…+c k (1) 若X 1≠X 2≠…≠X k 则A n =X k n 11+X k n 22+…+X k k n k (2) 若所有特征根X 1,X 2,…,X s.其中X i 是特征方程的t i 次重根,有t 1+t 2+…+t s =k 则A n=X n Q n )(11+X n Q n )(22+…+X n Q s n s )( ， 其中)(n Q i =B 1+n B 2+…+n B ti ti 1 -（B 1,B 2，…，B ti 为待定系数）
采用数学归纳法可以求解这一问题，然而这样做太过繁琐，而且在猜想通项公式中容易出错，本文提出一种易于被学生掌握的解法——特征方程法：针对问题中的递推关系式作出 一个方程称之为特征方程；借助这个特征方程的根快速求解通项公式.下面以定理形式进行阐述. 定理1设上述递推关系式的特征方程的根为，则当时，为常数列，即 ，其中是以为公比的等比数列，即 . 证明：因为由特征方程得作换元 则 当时，，数列是以为公比的等比数列，故 当时，，为0数列，故（证毕） 定理2如果数列满足下列条件：已知的值且对于，都有 （其中p、q、r、h均为常数，且），那么，可作特征方程. （1）当特征方程有两个相同的根（称作特征根）时， 若则 若，则其中特别地，当存在使时，无穷数列不存在. （2）当特征方程有两个相异的根、（称作特征根）时，则， 其中 证明：先证明定理的第（1）部分.
作交换 则 ① ∵是特征方程的根，∴ 将该式代入①式得② 将代入特征方程可整理得这与已知条件矛盾.故特征方程的根于是③ 当，即=时，由②式得故 当即时，由②、③两式可得此时可对②式作如下变化： ④ 由是方程的两个相同的根可以求得 ∴ 将此式代入④式得
令则故数列是以为公差的等差数列. ∴ 其中 当时， 当存在使时，无意义.故此时，无穷数列 是不存在的. 再证明定理的第（2）部分如下： ∵特征方程有两个相异的根、，∴其中必有一个特征根不等于，不妨令 于是可作变换 故，将代入再整理得 ⑤ 由第（1）部分的证明过程知不是特征方程的根，故 故所以由⑤式可得： ⑥
∵特征方程有两个相异根、方程有两个相异根、，而方程与方程又是同解方程. ∴ 将上两式代入⑥式得 当即时，数列是等比数列，公比为.此时对于都有 当即时，上式也成立. 由且可知 所以(证毕) 注：当时,会退化为常数;当时,可化归为较易解的递推关系,在此不再赘述.
1、将方程x5 +5x3– 2x + 1 = 0 改写成各种等价的形式进行迭代，观察迭代是否收敛，并给 出解释。 （1）画图： x1=-6:0.01:6; x2=-3:0.01:3; x3=-1:0.01:1; x4=-0.8:0.01:-0.75; y1=x1.^5 +5*x1.^3-2*x1+1; y2=x2.^5 +5*x2.^3-2*x2+1; y3=x3.^5 +5*x3.^3-2*x3+1; y4=x4.^5 +5*x4.^3-2*x4+1; subplot(2,2,1),plot(x1,y1) ,title('子图(1)') ,grid on, subplot(2,2,2),plot(x2,y2) ,title('子图(2)'),grid on, subplot(2,2,3),plot(x3,y3) ,title('子图(3)'),grid on, subplot(2,2,4),plot(x4,y4) ,title('子图(4)') ,grid on, 由图可知x 的初值应在（-0.78，0.76）之间。 （2）解：第一步构造迭代函数 x f x ()
53512 x x x ++= 1()x f x = 32121555x x x x =-+- 2()x f x = 32521x x x x =-+- 3()x f x = 第二步 利用加速迭代收敛法变形后： 5342 41012515x x x x x --+=-- 1()x f x = 62352435322 x x x x x x x --=++- 2()x f x = 2 5328561 x x x x x x -+=++- 3()x f x = 第三步 迭代 设定初值 00.75x =- 1()n n x f x +=n=0,1,2,3……… 用 MA TLAB 编程 x=-077;y=-0.77;z=-0.77; for k=1:30 x=(-4*x^5-10*x^3+1)/(2-5*x^4-15*x^2); y=(2*y^6+4*y^2-3*y)/(5*y^3+3*y^5+2*y-2); z=(8*z^2-2*z)/(z^5+5*z^3+6*z-1); x,y,z; end 迭代结果为： x = -61.5948 y = -0.7685