第二章 母函数与递推关系
2.1 求序列{0,1,8,27,??，n3,??}的母函数.
[解]设其母函数为A(x)?0?x?8x?27x????nx???方法一：由于1?x?x????x????2n233n
11?x12两边求导：0?1?2x?3x3????nxn?1????（1?x）
x(1?x)2同乘以x： xB'(x)?x?2x2?3x3????nxn?????
两边求导： B'(x)?xB''(x)?1?22x?32x2????n2xn?1????
1?(1?x)?x?2(1?x)(?1)(1?x)42 ??1?x(1?x)3
两边同乘以x：xB'(x)?x2B''(x)?x?22x2????n2xn????x(1?x)(1?x)3
两边求导： 1?23x?32x2????n3xn?1???
?(1?2x)(1?x)?x(1?x)?3(1?x)(?1)(1?x)46232
?(1?x)3233
(1?2x)(1?x)?3(1?x)x?1?4x?x(1?x)n4两边同乘以x：x?2x?3x????nx????3x(1?4x?x)(1?x)42
即A(x)?x(1?4x?x)(1?x)42
方法二：令n?A??3?n?3??n?2??n?1???????B?C?D ??????3??2??1??n?3??n?2??n?1?则有 0?A? ① ?3???B??2???C??1???D?A?B?C?D ??????
1= A??3???B??2???C??1???D?4A?3B?2C?D ② ???????4??3??2?【第 26 页 共 129 页】
8=A??3???B??2???C??1???D?10A?6B?3C?D ③
?????? 27=A??3???B??2???C??1???D?20A?10B?4C?D ??????1=3A+2B+C ⑤ 8=9A+5B+2C ⑥
27=19A+9B+3C ⑦ 6=3A+B ⑧ 24=10A+3B 6=A
⑨ ⑩
③－①有
⑦－3*⑤ 有
?6??5??4??5??4??3? ④
于是 ②－①有
于是 ⑥－2*⑤ 有 于是有⑨－3*⑧有 将⑩代入⑧有 将⑩，⑾代入⑤有 ?A?6??B??12故解为：?
?C?7?D??1?B=6-3A=6-3*6=-12 ⑾
C=1-3A-2B=1-3*6-2*(-12)=7
将⑩，⑾，⑿代入⑨有D=-A-B-C=-6-(-12)-7=-1
于是有n?6??3?n?3??n?2??n?1???????12?7?1 ??????3??3??1??n故此 母函数 A(x)??n3xn?0
?n?3??n?2??n?1?n?????[6??12??7??1]x??????n?0?3??2??1??????n?3?n?n?2?n?n?1?nn??????6??x?12?x?7?x??x?3??2??1?n?0n?0n?0n?0??????? ?6?1(1?x)4?121(1?x)43?721(1?x)23?11?x
6?12(1?x)?7(1?x)?(1?x)(1?x)x(x?4x?1)(1?x)42??3??4?2.2 已知序列{??3??,??3??,...????????n?3??,...},求母函数 3???n?3?n??3??x?... ???3??3??A(x)?[解]设其母函数为?3?????4??x?...?????【第 27 页 共 129 页】
则A(x)?1(1?x)3?1?1(1?x)4
2.3 已知母函数G(x)?3?78x1?3x?54x2,求序列{an}
［解］由于G(x)?3?78x1?3x?54x2?3?78x(1?6x)(1?9x)?A1?6x?B1?9x
则有A(1?9x)?B(1?6x)?(A?B)?(?9A?6B)x?3?78x A?B?3....①?于是有?
??9A?6B?78.....②由②－6*①有 故此 将④代入①有 从而有??A??4?B?7-15A=60 ③ A=-4 ④ B=3-A=3-(-4)=7
471?9xn故此G(x)??1?6x??
?n??4?(?6x)?7?(9x)n?0?n?0n
nn??[7?9n?0?(?1)n?14?6]xnn?1n故此：an?7?9?(?1)?4?6
2.4 已知母函数
3?78x1?3x?54x2,求对应的序列{an}.
［解］由于G(x)?3?9x1?x?56x2?3?9x(1?7x)(1?8x)?A1?7x?B1?8x
则有A(1?8x)?B(1?7x)?(A?B)?(?8A?7B)?3?9x
?A?2?B?1?于是有?,故此G(x)?21?7x?n?11?8x
?n?n?2?(?7x)?n?0?(8x)n?0n??[2?(?1)n?0n?7?8]x?nnn?[8n?0n?(?1)?2?7]x
nnn故
an?8?(?1)?2?7
n2.5 设Gn?F2n,其中Fn是第n个Fibonacci数。证明：
【第 28 页 共 129 页】
Gn?3Gn?1?Gn?2?0,n?2,3,4...求{G0,G1,G2,..}的母函数
[证]Gn?3Gn?1?Gn?2?F2n?3F2(n?1)?F2(n?2)?F2n?3F2n?2?F2n?4?(F2(n?1)?F2n?2)?3F2n?2?F2n?4
?F2(n?1)?2F2n?2?F2n?4?(F2n?2?F2n?3)?2F2n?2?F2n?4??F2n?2?F2n?3?F2n?4??F2n?2?F2n?2?02
设G(x)?G0?G1x?G2x?......x:G2?3G1?G0?0x:G3?3G2?G1?0x:G4?3G3?G2?0.....?G0?0??G1?F2?1.?G?F?34?2(G(x)?G0?G1x)?3x(G(x)?G0)?xG(x)?0G(x)?(x?3x?1)?x?0G(x)?xx?3x?13?25,??3?25,???1
222234
解其根为?? 故G(x)?x(1??x)(1??x)?A1??x?B1??x
A(1??x)?B(1??x)?x
?A?B?0....① ??A??B??1....②?1?A??????有?
1?B???????【第 29 页 共 129 页】
于是有 G(x)?1???1??x?(1?11??xn)
?1?nn
?????(??x?n?0??n?0nnx)n??n?01??
(???)xn
即 Gn?15151???3?21?2(???)
nn?[(5)?(2nn3?21?25)]2nn
?[(5)?(5)]
?F2n2.6 求序列{1,0,2,0,3,0,4,0,??}的母函数
[解] 令G(x)?1?2x2?3x4?4x6?......?nx2(n?1)?...... ?x2G(x)?x2?2x4?3x6?.......?(n?1)x2(n?1)?nx2n?......
而 (1-x)2G(x)?1?x2?x4?x6?.......?x2(n?1)?x2n?......
?11?x2
故此G(x)?1(1?x)222
2.7 设G(x)?1?2x?3x?4x?......?n?1x
求(1?x)G,(1?x)G.
1(1?x)22222462n?......
[解]根据题2.6可知G?
从而(1?x)G?21(1?x)22
并且(1?x)G?1
22.8 求下列序列的母函数： (a)1,0,1,0,1,0,?? (b)0,-1,0,-1,0,-1,??
【第 30 页 共 129 页】