用生成函数求解递推关系

§4用生成函数求解递推关系一、生成函数的定义,,,,,210nhhhh对给定数列nnxhxhxhhxg2210)(令的生成函数。为数列称nhxg)(给定数列生成函数求和展开例1xxxxxg11......1)(n2例2组合数：例31,xnnnnnC,C,C,C210nnnnnnnxxCxCxCCxg)1(...1)(2210牛顿二项系数：,C,,C,C,C210n1,)1()(0xxxCxgnnn,是任意实数例4,2,1,0,C)1(C1nhnknnknn1,)1(1)()(001xxxCxCxgknnnknnnkn的非负整数解的个数方程nxxxk...21,1nh常函数例5.,4321022222的生成函数，，，，求,n,解nnnxnxgnh022)(,...11132xxxx由于...4321)11322xxxx（求导...4321)14322xxxxx（因此...4321)11322223xxxxx（再导...432)1)1()(4232223xxxxxxxxg（得到二、常用求和公式),(),(}{},{xBxAbann的生成函数分别是设xnnnndxxAxxBanbxxAxBnab0)(1)(,11)(')(,.1则若则若)()()(....200110xBxAxCbabababacniininnnn则若逐项求导逐项积分柯西乘积xxAxBaaabnn1)()(,....310则若xxxAAxBaaabnkknnn1)()1()()(....41则收敛若0100)1(/1)()1(1.5nnnnnknnnnknnnnkkxrCxrCrxrxCrx最常用展开式：证明321022:aaabxn210:aaaabxnnxxaxxaxaxB1111)(2210101:aabx00:1abxxAxaxaax1)(112210证明410222)1(:aaAabx-1n10)1(:aaaAbxnnxxaxxaxAxB1111)1()(2100211)1(:aAaabx)1(:12100AaaabxxxAAxaxaaxxxA1)()1(11)1(2210例61111)(2naxxxxAnnnabxxxxB32321)(21)(')(xxxxAxB011003212)1()(bababancxnnxCnnnnnn321111)()()(xxxxxxBxAxC0122)2(211nnnnxCxnnnnnnnnnnnCCCa2)1(22211112例7解133221...)(nnnxfxfxfxfxg设01,102121fhhfffnnn求解递推式1233:fffx......:nx)(])([)(22xgxxxgxxxxg三、求解常系数齐次递推式2344:fffxxxxxxxxg222)()1)((21)(xxxxg怎样展开？21)(xxxxg展成部分分式xxxxg251-1251-1)(xxxg251-1151251-1151)(00n0n25151251512515125151nnnnnnnnxxxnnnf2515125151例8解0332210...)(nnnxhxhxhxhhxg设2,1651021hhhhhnnn求解递推式,2,1,0,34-25nhnnn得012265:hhhx123365:hhhx234465:hhhx......:nx)(6]1)([521)(2xgxxgxxxgxxxxxxg31421565171)(2解出000)3425()3(4)2(5nnnnnnnnxxx例9解0332210...)(nnnxhxhxhxhhxg设1,10,02061210321hhhhhhhnnnn求解递推式02016:01233hhhhx......:nx2)(xxxg])([xxgx]0)([162xgx)(203xgx02016:12344hhhhx02016:23455hhhhx0xxxxxxxxxxxg511495)21(171211492)51()21(20161)(2232解出000)5(495)2)(1(71)2(492nnnnnnxxnx0(-5)4952)1(712492nnnnnxnnnnnnh(-5)4952)1(712492例4解2...)(332210xhxhxhhxg1,10,02061210321hhhhhhhnnnn求解递推式)()20161(32xgxxx0)16()(2012010xhhhxhhh...)(4332210xhxhxhxhxxg...161616-)(164231202xhxhxhxgx...2020)(2041303xhxhxgxxxx2)01611()01(03220161)(xxxxxg解出例4解30332210...)(nnnxhxhxhxhhxg1,10,02061210321hhhhhhhnnnn求解递推式0)2016(3321nnnnnnxhhhh3220161)(xxxxxg解出02016033332223113nnnnnnnnnnnnxhxxhxxhxxh0)(20)(16)()(322xgxxgxxxgxxxxg定理给定阶递推式1102211,,,0...kknknnnhhhhahahahk)()()(:xqxpxG则生成函数必为kkxaxaxaxq2211)()1(kkkaxaxxr11)()2(特征函数：)1()1)(1()()())(()()3(2121xxxxqxxxxrkk若101322112021120110)()()()()4(kkkkkxhahahahxhahahxhahhxp由递推关系确定由初始条件确定