《组合数学》 第三章 递推关系
A(x)＝
将A(x)展开
A(x)＝c1＝＝
c1c2?2?? 21?3x1?2x?1?2x?n?0???3x?1n?n＋c2
n?0??2x??n－2
n?0n???? n?12x??n?0???c3?c22n??n?1?2n?1xn
?n?0nax?n
比较等式两端xn的系数
an＝c13n＋c22n－(n＋1)2n?1
式中c1、c2为任意常数，由初值a0和a1确定。 例如，设a0＝1，a1＝－2，则c1、c2满足下列方程组
?c1?c2?2?1 ??3c1?2c2?8??2解得c1＝0，c2＝3 .
因此满足上述初值条件的递推关系的解为
an＝3×2n－(n＋1) 2n?1＝(1－2n) 2n
?Fn?Fn?1?Fn?2 【例3.3.6】求定解问题? .
?F1?F2?1（解）（思路：拆项）。 反推求 F0＝F2－F1＝0
31／72
《组合数学》 第三章 递推关系
设{ Fn}的母函数为G(x)＝?Fnxn
n?0?根据递推关系有
G(x)＝0＋x＋??Fn?1?Fn?2?xn
＝x＋x?Fn?1xn?2n?2?n?1?＋x2?Fn?2?n?2x n?2G(x)＝x＋x G(x)＋x2 G(x)
xG(x)＝ （3.3.1） 21?x?x利用“待定系数法”展开G(x)为幂级数，
xG(x)＝
?1?5??1?5??1???x??1?x???22????AB?＝
1?51?51?x1?x22?5?15?1???A?B???A?B?x?22?? G(x)＝
?1?5??1?5??1??1?x?x?????22?????A?B?0?得A、B应满足的方程 ?5?1 5?1A?B?1??2211解之得 A＝，B＝－
55???1?11∴ G(x)＝???
5?1?51?5?1?x1?x????2232／72
《组合数学》 第三章 递推关系
1?51?5展开G(x)，令??，??
221?11?G(x)＝ ???5?1??x1??x?＝＝
∴ Fn＝说明：
? 此为著名的Fibonacci数列（见§3.4）。
? 一个事实，虽然Fn都是正整数，但它们却可由一些无理数表示出来。 【例3.3.7】解定解??n?1?an??n?2?an?1?2an?2?0,?n?2?。 ??a0?0,a1?1（解）根据方程的特点，令
A(x)＝a1＋a2x＋a3x2＋a4x3＋?＋anxn?1＋?
两边对x求导
A'(x)＝2a3x＋3a4x2＋?＋(n－1)anxn?2＋?
（注意由原问题知a2＝0），计算A'(x)－x A'(x)，得
(1－x)A'(x)＝2a3x＋(3a4－2a3)x2＋(4a5－3a4)x3＋?
＋[(n－1)an－(n－2)an－1]xn?2＋? ＝2a1x＋2a2 x2＋2a3 x3＋?＋2an－2xn?2＋? ＝2x A(x)
（注意原方程可化为 (n－1)an－(n－2)an－1＝2an－2，a3＝a1）
33／72
?1??nn???x?????x?? ??5?n?0n?0?1?n????n?xn ?5n?0nn?????11?51?5?nn????? ???＝?????5??2??2?????1?5?问题
《组合数学》 第三章 递推关系
A??x?2x2x即 ＝＝－2＋
A?x?1?x1?x注意到A?x?x?0?a1?1，两边对x积分得
xA??x??0A?x?dx＝－2x－2ln(1－x)
即 lnA(x)＋ln(1－x)2＝－2x
∴ A(x)＝e?2x／(1－x)2
展成幂级数
????2x?n????n?1?n?????A(x)＝ ? x?????n!?????n?0??n?0?1????n?-1?k2k?n?＝ ????k!?n?k?1?x?
?n?0k?0?n∴ an＋
?n?k?1?2k 1＝??-1?kk?0k! 【例3.3.8】（用指母函数求解）：求解递推关系
?Dn?nDn?1???1?n??D1?0?n?2?
（解）由原方程反推可得D0＝D1－(－1)0＝1。
观察：Dn随n的增大而急剧增大，有点象n!，故用指母函数。
?xn令 D(x)＝ ?Dn
n!n?0xn用乘以原方程的两端，并对n从1到∞求和，得 n!n??xnxnnxDn＝?nDn?1＋???1? ?n!n?1n!n?1n!n?1?与母函数比较 D(x)－D0＝xD(x)＋e?x－1
e?x亦即 D(x)＝
1?x34／72
《组合数学》 第三章 递推关系
n??1? Dn由母函数的性质3 ＝?n!k?0k!k?11n1????∴ Dn＝n!? 1??????1?1!2!?n!???an?3an?1?2bn?1? 【例3.3.9】用母函数方法求解二?bn?an?1?bn?1.
?a?1,b?0?00（解）设数列?an?、?bn?的母函数分别为A?x?、B?x?。 方程一两边同乘以xn得 anxn?3an?1xn?2bn?1xn 两边对求和：
?anx＝3x?an?1xnn?1n?1??n?1?2x?bn?1xn?1
n?1?即 A?x?－a0＝3xA?x?＋2xB?x? 代入初值并整理： (1－3x)A?x?－2xB?x?＝1 ①
同理，由方程二可得 xA?x?＋(x－1)B?x?＝0 ② 联立方程①、②解之
1?x???Ax???1?4x?x2 ?x?B?x???1?4x?x2?函数分解：
A?x?＝3?3613?31 ?61?2?3x1?2?3x????B?x?＝3131 ?61?2?3x61?2?3x????幂级数展开
35／72