二、非线性递推数列 目的要求：掌握常见的非线性递推数列的通项求法（化为：一阶线性、恒等变形、 不动点法、数归法、母函数法等） 重点：（难点）根据其特点采用相应方法求n a 1、分式递推数列：b
aa d
ca a n n n ++=+1
⑴ 若0=d ，则
c
a
ca b ca b aa a n n n n +=+=
+1
1 令其为c
a
b c b b n n +=+1 （一阶线性……）
⑵ 若0,0≠≠c d ，用不动点法（P166 TH10） 例1、1,1
211=+=
+a a a a n n
n n ，求n a
解：n n
n a a 21
11
+=
+即n n n b b 21+=+ 则()
1
21
122212
12121
1-=
∴-=+-=--+
=-n n n n n n a b b 例2、1,924111==+-++a a a a a n n n n ，求n a 解：变形：()4
9
211-+-+=
+=++αααn n n n b b b a
()()
4
9
6221
-++---=
+ααααn n n b b b 令0962=+-αα（化为⑴型） 321==αα 则11
11
1
1-=
--
=++n
n n n n b b b b b ⎭
⎬⎫
⎩⎨⎧n b 1是等差且常…
1
25
6212
2
1111--=
∴-=
∴-=-=∴
n n a n
b n n b b n n n 题中α恰好是x x x =--492的根，即α为()4
9
2--=x x x f 的不动点 TH9 P166
TH10 P166 ()() d
cn b
an n f -+=
则① ⎭⎬⎫
⎩⎨⎧--21ααn n u u 是等比……
② ⎭
⎬⎫
⎩⎨⎧-p u n 1是等差……
2、其他非线性递推数列
恒等变形后 ⎪⎪⎪⎪⎩⎪
⎪⎪⎪
⎨⎧母函数法数归迭代分式线性等差（等比）
（书上例10、11、12）
例10、{}()33,2,1,2
1
1321≥+=
===--+n a a a a a a a a n n n n n ，求n a
解：变形1213--++=n n n n a a a a （21,-+n n a a 非连续二项） 2133---+=n n n n a a a a
211321-----+-=-⇒n n n n n n n n a a a a a a a a ()()11231-+---+=+⇒n n n n n n a a a a a a 即：
2
3
111----++=
+n n n n n n a a a a a a （为常数列） ()43
2
1
311==+=+∴-+n a a a a a a n n n
113-+-=∴n n n a a a 二阶常线性齐次…… =∴n a （特征根法）
例12、()310,10,13
1
2221≥===--n a a a a a n n n
解：变形212
110---⋅=⎪⎪⎭
⎫ ⎝⎛n n n n a a a a ，即：1
12
10--==n n
n n n a a b b b 迭代()()2
2
2
1
221
4
12
14
122
12
1
1101010101010--⋅⋅====∴--n n b b b b n n n
()212
1
2
1121
122
1110
1010
10
2
2
2
2
b b a a n n n n n →=⋅=⎪⎪⎭
⎫ ⎝⎛⋅=--
-
----
111010--==∴n n n a a 例11、{}()
1211102,2
5,2,u u u u u u u n n n n --===-+ 求证：[]()3
122
n
n n u --=
解：（猜测后证明）适用于递推关系复杂，不便求n a （或证明n a ）
1=n 时，()()3
12312122
2
22
222---
---+=+=n u 2=n 时，()()3
123
12133
33
32
2
88---
---+=+=u
1）猜测：()()3
123
122
2n
n n
n n u ---
--+=
（再证：()3
122
n
n --为整数，则()3
122
n
n ---
为（0，1）内的纯小数）
2）数学归纳法证明，设()()3
12n
n n f --= n=0、1、2显然成立
假设n=k 时，结论成立，则n=k+1时
由()
12
112u u u u k k k --=-+
()()()()()()2
5
22221212-
++=----k f k f k f k f ()()()()[]()()()()2
5222212121212-
+++=-+----+--+k f k f k f k f k f k f k f k f 又()()()()()()⎩⎨⎧-=-+-+=-+k k f k f k f k f k f 112112 则()()()()2
5
2222111111
-
+++=--+-+++k
k k f k f k u （()()k k 11221--++ 为记k 取 ()()1122+-++=k f k f 奇、偶数，恒为2
5
）
猜测成立
2）再证()n f 为整数
()()()()
3
221231221 +-+=
--=--n n n
n n f ()n f ∴为整数，()n f -2为（0，1）内的纯小数 ∴对任意自然数n ，[]()3
122n
n n u --=
例15、母函数法
将数列n n n n C C C ,,,10 当多项式函数()n
n n n n x C x C C x f ++=10
联系是研究组合数性质的有效方法之一
一般：多项式n n x a x a a +++ 10称为数列n a a 0的母函数（有限、无限均可） 而母函数∑∞
=0n n n x a 可求和函数，从而可借助母函数求线性递推数列的通项
例15、()265,2,12110≥-=-==--n a a a a a n n n 解：（显然特征根法可求n a ）现用母函数法
令() ++++=n n n x a x a a x f 10 ①
∴=+---06521n n n a a a 设法求出()x f ，即可求n a
寻求()n n n n x a a a 6,51--
由() -----=--n n x a x a x a x xf 12105555 ② () +++=-n n x a x a x f x 2202666 ③
①+②+③得：()
()()()20120102655651x a a a x a a a x f x x +-+-+=+- ()x x a a a n n n n 716521-=++-++-- ()x
x x b x a x x x x f 314
2153121651712---=-+-=+--=
∴
()()()
∑∑∑∞∞∞⋅-⋅=-=0
34253425n n n n
n
x x x n n n a 3425⋅-⋅=∴。