《组合数学》 第三章 递推关系
?an?nan?1?n!,【例3.2.12】解定解问题 ?a?2.?0n?1。
（解）线性变系数一阶非齐次递推关系。 难点： f?n??n!
an?1?an??1,n?1?观察： ?n!?n?1?!
?a?2?0?bn?bn?1?1,an令bn?，化为 ?n!?b0?2n?1
*nb特解： n?n， 通解： bn?B?1?n
an的通解： an??n?2?n!.
另法：对于bn，可以用迭代法或直接观察出bn?n?2，
再用归纳法证明之即可。
【例3.2.13】设n≥1时，an≥0，解定解问题
22?an?2an?1?1,??a0?2n?1。
（解）常系数非线性二阶递推关系。
?bn?2bn?1?1,n?1令bn?a，变为： ?，
?b0?4解之得bn?5?2n?1，从而an?5?2n?1。
2n
§3.3 解递推关系的其它方法
§3.3.1 迭代法与归纳法
适应情况：
26／72
《组合数学》 第三章 递推关系
1. 迭代法：对某些一阶的递推关系，使用迭代法求解可
能更快。 2. 归纳法：观察n比较小时an的表达式的规律，总结或
猜出an的一般表达式，然后用归纳法证明。
?an?2an?1?2n,?n?1?【例3.3.1】?
?a0?3anan?1（解）变换 n?n?1?1
22逐步迭代：
anan?1an?2a0?n?1?1?n?2?2???0?n?n?3 n2222∴ an?2n?n?3?,?n?1?
当n＝0时，上式仍成立（即满足所给的初值），故解为
an?2n?n?3?,?n?0?
an另法：先做变量代换bn?n（n＝1, 2, ?），得
2?bn?bn?1?1,?n?1? ?
?b0?3迭代求解： bn?n?3， ?n?0?
然后反代回去得 an?2nbn＝2n?n?3?， ?n?1?
n??an?nan?1???1?, 【例3.3.2】解递推关系???a0?3?n?1?。
nanan?1??1?（解） 因 ，?n?1? ??n!(n?1)!n!27／72
《组合数学》 第三章 递推关系
n?1nanan?2???1??1?迭代得 ＝ ??n!(n?2)!(n?1)!n!＝??
?a0??1???1??1?????＝? 0!1!2!n!12n＝3??k?1n??1?kk!?2??k?0n??1?k
k!kn???1?所以 an?n!??2??k!k?0???,???n?1?
当n＝0时，上式仍成立，故定解问题的解为
kn???1?an?n!??2??k!k?0???,???n?0?
?an?4an?2,?n?2?【例3.3.3】解递推关系?。
?a0?2,a1?1（解）由题设
a2k?1?22a2k?1?24a2k?3???22ka1
a2k?22a2k?2?24ak?4???22ka0
2k2k?1a?2a?2所以 2k?1， 2k，?k?1?
当k＝0时，上面两个式子仍成立。故
?2n?1,当n为奇数时an??n?1?2,当n为偶数时
28／72
《组合数学》 第三章 递推关系
或
an?2n???1?n，?n?0?
?an?an?1?n3 【例3.3.4】用归纳法解递推关系?， ?n?1?
?a0?0（解）计算较小n时的an，并观察得
a0?0?02
a1?1?12??1?0?
2a2?13?23?9??0?1?2?
2????
由此可猜想
a3?13?23?33?36??0?1?2?3?
2n2?1?n??n?1?n??2 an＝?0?1?2?...?n?????2?4?22再用归纳法证之：显然n＝0，1，2，3时结论为真。
k2?1?k?假设n＝k时结论为真，即ak＝成立。
42考虑n＝k＋1时 ak?1＝ak??k?1?
3?k?1??k?2?k2?1?k?3???k?1?＝
44222n2?1?n?结论成立。故对一切非负整数n，有an＝。
42§3.3.2 母函数方法
思路：对较复杂的递推关系，利用母函数求解。 方法：
29／72
《组合数学》 第三章 递推关系
? 设欲求解的数列{ an} 的母函数为G(x)＝
nax?n； n?0?? 利用递推关系本身求函数G(x)满足的方程（代数方程
或微分方程等）； ? 解方程求出G(x)；
? 将G(x)展开成x的幂级数。则xn的系数便是an的解析表达式（即递推关系的解）。 【例3.3.5】解递推关系
an－5an－1＋6an－2＝2n， n≥2
（解）（利用无穷求和）： 令A(x)＝
nn
，原方程两边同乘x得 ax?nn?0??an?5an?1?6an?2?xn?2nxn
n即 anxn?5an?1xn?6an?2xn??2x?
对n从2到∞求和得
n?2???axn?n?5an?1x?6an?2x??nn????2x?n?2?n
n?2?nnnn??－5＋6＝ axaxax2x?n?n?1?n?2?n?2n?22?n?2?n?2?anx－5x?anx＋6xn?nn?1n??＝ ax2x?n?nn?02
?n?21(A(x)－a0－a1x）－5x(A(x)－a0)＋6xA(x)＝－(1＋2x)
1?2x解之得
a0??a1?5a0?x4x2?A(x)＝ 22?1?5x?6x??1?2x?1?5x?6x30／72