1、2 2.1 递推关系递推关系Hanoi塔问题：这是组合数学中的一个著名问题。塔问题：这是组合数学中的一个著名问题。n个圆盘依其半径大小，从下而上套在个圆盘依其半径大小，从下而上套在A柱上。每柱上。每次只允许取一个移到柱次只允许取一个移到柱B或或C上，而且不允许大盘上，而且不允许大盘放在小盘上方。若要求把柱放在小盘上方。若要求把柱A上的上的n个盘移到个盘移到C柱柱上，请设计一种方法并估计要移动几个盘次。现上，请设计一种方法并估计要移动几个盘次。现在只有在只有A、B、C三根柱子可用。三根柱子可用。首先要设计算法，进而估计它的复杂性，即估计工首先要设计算法，进而估计它的复杂性，即估计工作量。作量。3
2、 当当n=2时，时，第一步把第一步把A柱的小圆盘移到柱的小圆盘移到B柱；柱；第二步把第二步把A柱的大圆盘移到柱的大圆盘移到C柱；柱；A B C第三步把第三步把B柱的小圆盘移到柱的小圆盘移到C柱，即完成移动。柱，即完成移动。4 假定假定n-1个盘子的转移算法已经确定，对于一般个盘子的转移算法已经确定，对于一般n个个圆盘的问题，圆盘的问题，A B C 首先把首先把A柱上面的柱上面的n-1个圆盘移到个圆盘移到B柱；柱；然后把然后把A柱最下面的圆盘移到柱最下面的圆盘移到C柱；柱；最后把最后把B柱的柱的n-1个圆盘移到个圆盘移到C柱，即完成移动。柱，即完成移动。5 令令h(n)表示表示n个圆盘所需要的转
3、移盘次。个圆盘所需要的转移盘次。因此有：因此有：( )(),( ).h nh nh21111从这个递推关系式可以逐项递推得到所有的从这个递推关系式可以逐项递推得到所有的h(n)。根据算法先把前面根据算法先把前面n-1个盘子转移到个盘子转移到B上；然后把第上；然后把第n个盘子转到个盘子转到C上；最后将上；最后将B的的n-1个盘子转移到个盘子转移到C上。上。下面我们利用母函数来得到下面我们利用母函数来得到h(n)的通项表达式。的通项表达式。假设序列假设序列h(n)对应的母函数为对应的母函数为H(x)，即，即( )( )( )( )H xhxhxhx231236 ( )( )( )( )H xhxh
4、xhx23123) ( ) -( )( ),xH xhxhx2322122,xxxxx 231_()( )( ) ( )( ) ( )( )x H xhxhhxhhx 23121221322因此有因此有 ( ).xH xxx 1127 或者利用或者利用( )( )hh 2211( )( )hh 3221( )( )hh 4231x2:x3:x4:_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ ( )( )/()H xxxH xxx221+)同样可以得到：同样可以得到： ( ).xH xxx 1128 假设假设 ( ).xABH x
5、xxxx112121下面我们用幂级数展开的方法得到下面我们用幂级数展开的方法得到h(n).( )H xxx11121()nnnnxx002利用待定系数法容易得到利用待定系数法容易得到A=1，B=-1，即，即(),nnnx 121即即( ).nh n 219 2.2 母函数母函数母函数方法是一套非常有用的方法，应用极广。母函数方法是一套非常有用的方法，应用极广。这套方法的系统叙述，最早见于这套方法的系统叙述，最早见于Laplace在在1812年年的名著的名著概率解析理论。概率解析理论。我们来看如下的例子我们来看如下的例子：两个骰子掷出两个骰子掷出6点，有多少点，有多少种选法？种选法？注意到，出现
6、注意到，出现1，5有两种选法，出现有两种选法，出现2，4也有两也有两种选法，而出现种选法，而出现3，3只有一种选法，按加法法则，只有一种选法，按加法法则，共有共有2+2+1=5种不同选法。种不同选法。或者，第一个骰子除了或者，第一个骰子除了6以外都可选，有以外都可选，有5种选法，种选法，一旦第一个选定，第二个骰子就只有一种可能的选一旦第一个选定，第二个骰子就只有一种可能的选法，按乘法法则有法，按乘法法则有51=5种。种。10 但碰到用三个或四个骰子掷出但碰到用三个或四个骰子掷出n点，上述两方法就点，上述两方法就不胜其烦了。不胜其烦了。设想把骰子出现的点数设想把骰子出现的点数1,2,6和和t,t
7、2,t6对应起来，对应起来，则每个骰子可能出现的点数与则每个骰子可能出现的点数与(t+t2+t6)中中t的各次的各次幂一一对应。幂一一对应。若有两个骰子，则若有两个骰子，则(.)(.).ttttttttttt2626234562345其中其中t6的系数为的系数为5，显然来自于，显然来自于, ,. ttttttttttttttt156246336426516这表明，这表明，掷出掷出6点的方法一一对应于得到点的方法一一对应于得到t6的方法的方法。11 262( )(.)f tttt故使两个骰子掷出故使两个骰子掷出n点的方法数等价于求点的方法数等价于求中中tn的系数。的系数。这个函数这个函数f(t)
8、称为称为母函数母函数。母函数方法的基本思想：母函数方法的基本思想：把离散数列和幂级数一一对应起来，把离散数列间把离散数列和幂级数一一对应起来，把离散数列间的相互结合关系对应成为幂级数间的运算关系，最的相互结合关系对应成为幂级数间的运算关系，最后由幂级数形式来确定离散数列的构造。后由幂级数形式来确定离散数列的构造。12 再来看下面的例子：再来看下面的例子：nnnnnna xa xa xaaaxa aa aaaxa aa x 121221213112(1)(1)(1)1()(),若令若令a1=a2= =an=1，则有，则有()( , )( , )( , ).nnxC nxC nxC n n x21
9、112这就是二项式展开定理。这就是二项式展开定理。13 () ()()111mnm nxxx ( , )( , )( , ) (, )(, )(,)(, )(, )(,)010101nmmnC nC nxC n n xC mC mxC m m xC mnC mnxC mn mn x 比较等号两端项对应系数，可以得到恒等式：比较等号两端项对应系数，可以得到恒等式：(, )(, ) ( , ) (, ) ( ,) (, ) ( , ).0110C mn rC mC n rC mC n rC m r C n14 () (/)()1111nmmm nxxxx ( , )( , )( , ) (, )(
10、, )(,) (, )(, )(, ) (,)120101012nmmm nC nC nxC n n xC mC mxC m m xxC mnC mnxC mnxC mn mn x (,)( , ) (, )( , ) (, ) ( ,) (,). C mn mC nC mC nC mC n m C m m0011比较等式两端的常数项，可以得到恒等式：比较等式两端的常数项，可以得到恒等式：15 nnxC nC nxC n n x(1)( ,0)( ,1)( , )中令中令x=1 可得可得又如在等式又如在等式nC nC nC nC n n( ,0)( ,1)( ,2)( , )2 .两端对两端对
11、x求导可得：求导可得：()( , )( , )( , ),nnnxC nC nxnC n n x111122再令再令x=1 可得可得nC nC nC nnC n nn1( ,1)2 ( ,2)3 ( ,3)( , )2.类似还可以得到类似还可以得到nC nC nn C n nn n222( ,1)2( ,2)( , )(1)2.16 还可以类似地推出一些等式，但通过上面一些例子还可以类似地推出一些等式，但通过上面一些例子已可见函数已可见函数(1+x)n在研究序列在研究序列C(n,0),C(n,1),C(n,n)的关系时所起的作用。的关系时所起的作用。定义：对于序列定义：对于序列a0,a1,a2
12、,，函数，函数G xaa xa x2012( )称为序列称为序列a0,a1,a2,的母函数。的母函数。例如函数例如函数(1+x)n就是就是序列序列C(n,0),C(n,1),C(n,n)的的母函数。母函数。如若已知序列，则对应的母函数可根据定义给出。如若已知序列，则对应的母函数可根据定义给出。反之，如果已经求出序列的母函数反之，如果已经求出序列的母函数G(x)，则该序列，则该序列也随之确定。也随之确定。17 2.3 Fibonacci数列数列Fibonacci数列是递推关系的又一个典型问题，数数列是递推关系的又一个典型问题，数列的本身有着许多应用。列的本身有着许多应用。有雌雄兔子一对，假定过两
13、月便可繁殖雌雄各一的有雌雄兔子一对，假定过两月便可繁殖雌雄各一的一对小兔。问过了一对小兔。问过了n个月后共有多少对兔子？个月后共有多少对兔子？设满设满n个月时兔子对数为个月时兔子对数为Fn，其中当月新生兔数目，其中当月新生兔数目设为设为Nn 对，上个月留下的兔子数目设为对，上个月留下的兔子数目设为On对，则对，则.nnnFNO但是注意到但是注意到 On = Fn-1，Nn = On-1 = Fn-2，因此有，因此有,.nnnFFFFF1212118 利用这个递推关系很容易可以得到：利用这个递推关系很容易可以得到：, , , FFFFFFFFF31242353423325下面我们利用母函数来计算
14、下面我们利用母函数来计算Fn的通项表达式。的通项表达式。设设Fn的母函数为的母函数为G(x)，则，则FFF321FFF432x3:x4:_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _( )( ( )( )G xxxx G xxx G x22+)() ( )xx G xx 21( ).xG xxx 2119 ,151522方程方程1-x-x2=0的两个根设为：的两个根设为：则有则有( ).xABG xxxxx 2111利用待定系数法易有利用待定系数法易有,AB 1515因此有因此有( )()()nnnnG xxx 0015()nnn
15、nx 115即通项表达式为：即通项表达式为：().nnnF 1520 ( );nnFFFF 12231FFF132FFF243) nnnFFF21_nnnFFF11nnFFFFF 1222.nF 2121 ( );nnFFFFF 1352124FF 12FFF342) nnnFFF 21222_FFF564.nnFFFFF 13521222 ( ) .nnnFFFF F 2221215FF F 2121()FF FFF FF F222312321) () nnnnnnnnFF FFF FFF21111_()FF FFF FF F233423423.nnnFFFF F 22212123 2.5
16、母函数的性质母函数的性质设序列设序列ak, bk对应的母函数分别为对应的母函数分别为A(x), B(x)。则下面的两个性质显然成立：则下面的两个性质显然成立：(1) A(x)= B(x) 当且仅当当且仅当 ak= bk。(2) 若若A(x)+B(x)=c0+c1x+c2x2+，则，则ck=ak+bk。性质性质1：若：若 则则 B(x)=xlA(x)。0,kk lklbakl ( ) ( ).lllllllB xb xbxa xa xx A x 11101000证证:24 则则( )().!1211123mmmmxxxxB xxe 例例4 已知已知 ,!231123xxxxA xe性质性质2：若
17、：若bk=ak+l，则，则( ) ( )/.lklkkB xA xa xx 10则则( ).!xxxxB xexx 2221234例例5 已知已知 ,!231123xxxxA xe 25 性质性质3：若：若bk=a0+ak，则，则( )( ).A xB xx 1ba 00baa101baaa2012kkbaaaa0121:x:x2:xk:_ ( )/()/()/()B xaxa xxa xx2012111/()( )/().aa xa xxA xx201211+)26 则则( )B xxxx231234例例6 已知已知( ),nA xxxxx 2111( ),()A xxx2111( )C x
18、xxx2313610( ).()B xxx311127 性质性质4：若若bk=ak+ak+1+，则，则( )( )( ).AxA xB xx 11baaa0012( )baaaAa112301( )baaaAaa22340111:x:x2:_ ( )( )()() ()B xAxxa xxxa xxx2202211 111()( )( )( ).aa xxAAxA xxxx 0111111+)( )A 128 性质性质5：若：若bk=kak，则，则( )( ).B xxA x 性质性质6：若：若bk=ak/(1+k)，则，则( )( ).xB xA x dxx 01则则( )nB xxxxnx
19、2323例例7 已知已知( ),nA xxxxx 2111 .()xxxx 21 1129 性质性质7：若：若ck=a0bk+a1bk-1+ak-1b1+akb0，则，则( )C xcc xc x2012( ) ( ).A x B x ca b 000ca ba b10 110ca ba ba b2021 1201:x:x2:_ C xabb xb xa x bb xb xa xbb xb x2200121012222012 ( ) ( ).aa xa xbb xb xA x B x22012012+)30 令令 ,xB xxxxx 232231例例8 已知已知( ),nA xxxxx 211
20、1(),kknk nnk kca bk 01122( )( ) ( ).()xC xA x B xx 31则则31 线性常系数递推关系线性常系数递推关系2.6 线性常系数齐次递推关系线性常系数齐次递推关系2.7 线性常系数非齐次递推关系线性常系数非齐次递推关系32 2.6. 线性常系数齐次递推关系线性常系数齐次递推关系确定一个数列确定一个数列an的最常用的方法是：的最常用的方法是：(1) 给出一般项给出一般项an的表达式的表达式;(2) 得到该数列的母函数得到该数列的母函数;(3) 建立数列所满足的递推关系。建立数列所满足的递推关系。一个一个r-阶递推关系阶递推关系定义为：有正整数定义为：有正
21、整数r 以及一个以及一个r+1元函数元函数F，使得对所有，使得对所有n r, 有关系式有关系式(,.,; ).nnnn raF aaan 12这样若已知这个数列的前这样若已知这个数列的前r项项a0,a1,ar-1(称为初始称为初始条件条件)，则可以通过递推关系逐项确定整个数列。，则可以通过递推关系逐项确定整个数列。33 定义定义：如果序列：如果序列an满足满足( ), (1)nnnkn kaC aC aC ab n1122如果如果b(n)=0，则称为，则称为齐次齐次的，的，否则称为否则称为非齐次非齐次的。的。 , (2)kkad adad001111其中其中 都是常数，都是常数，,(),kkk
22、C CCCd dd 120110则则(1)称为一个称为一个k阶线性常系数递推关系阶线性常系数递推关系，(2)称为称为初始条件初始条件。34 , nnnab ac ac 1200先考虑二阶线性常系数齐次递推关系，即先考虑二阶线性常系数齐次递推关系，即令母函数为令母函数为G(x)=a0+a1x+a2x2+，则，则( ) G xaa xa x 2012( ) bxG xb a xb a x201)( ) cx G xc a x220_-() ( )()() ().nnnnbxcx G xaabaxabacaxabacax22010210121() .aabax01035 ()( ).aabaxG x
23、bxcx 01021因此有因此有 ,bbcr 21 242与分母相对应的方程与分母相对应的方程 x2+bx+c=0 称为称为特征方程特征方程，它，它的根的根称为称为特征根特征根。这样这样G(x)可以表示为：可以表示为： ()( ).aabaxG xr xr x 010121136 (1) 如果如果r1r2，则则 ()( )aabaxABG xr xr xr xr x01012121111下面要根据特征根来进行分类讨论。下面要根据特征根来进行分类讨论。()()nnnnAr xBr x1200(),nnnnArBrx 120因此通项表达式为：因此通项表达式为：,nnnaArBr12其中常数其中常数
24、A, B可以利用待定系数法确定，或者利用可以利用待定系数法确定，或者利用初始条件初始条件(A+B=a0, Ar1+Br2=a1)来确定。来确定。37 (1) 如果如果r1r2，且是一对共轭复根，且是一对共轭复根，则可以假设则可以假设-,iirere12 这样就有：这样就有：nnnaArBr12定义两个新的待定常数：定义两个新的待定常数： nniiAeBe ninninAeBe cossin.nnABniAiBn,kABkiAiB12则通项表达式为：则通项表达式为：cossin,nnnaknkn12其中其中k1, k2由初始条件决定。由初始条件决定。38 (2) 如果如果r1=r2，则可以令则可
25、以令r=r1=r2=-b/2， ()( )()aabaxABG xrxrxrx 01022111 (),nnnAB nr x 01因此通项表达式为：因此通项表达式为： ,nnaCDn r其中常数其中常数C, D可以利用初始条件来确定。可以利用初始条件来确定。例如，若已知例如，若已知a0, a1，则，则,aC 0 ,nnnCDn r x 0()aCD r1.Dara1039 -,nnnaaa12120例例1 求解递推关系：求解递推关系：,xx2120特征方程为特征方程为因此通项表达式可以设为：因此通项表达式可以设为：() .nnnaAB 43,.aa01326,.rr 1243解得特征根为解得特
26、征根为代入初始条件有代入初始条件有,aABaAB0134326,.AB 52因此通项表达式为：因此通项表达式为：() .nnna 5 42340 -,nnnaaa 12例例2 求解递推关系：求解递推关系：,xx210特征方程为特征方程为因此通项表达式可以设为：因此通项表达式可以设为：cossin.nnnaAB33,.aa1210,ir 1 2132解得特征根为解得特征根为代入初始条件有代入初始条件有,aABaAB 121313102222,.AB13 3因此通项表达式为：因此通项表达式为：.ie 3cossin.nnna333341 -,nnnFFF12例例3 Fibonacci数列：数列：,
27、xx210特征方程为特征方程为因此通项表达式可以设为：因此通项表达式可以设为：.nnnFA rB r12.FF 121,.r 1 2152解得特征根为解得特征根为代入初始条件有代入初始条件有,FABFArBr012201.AB 15因此通项表达式为：因此通项表达式为：.nnnF1151152255F 0042 -,nnnaaa12440例例4 求解递推关系：求解递推关系：,xx2440特征方程为特征方程为因此通项表达式可以设为：因此通项表达式可以设为：().nnaABn2,.aa0114.rr122解得特征根为解得特征根为代入初始条件有代入初始条件有,(),aAaAB01124,.AB11因此
28、通项表达式为：因此通项表达式为：().nnan1243 接下来讨论一般的接下来讨论一般的k阶线性常系数齐次递推关系：阶线性常系数齐次递推关系：.nnnkn kaC aC aC a11220类似的，令母函数为类似的，令母函数为G(x)=a0+a1x+a2x2+，则，则()kkkkkxaC aC aC a 112200()kkkkkxaC aC aC a 1112110()nnnnkn kxaC aC aC a11220_ kkiikiikiiG xa xC x G xa xC x G x121000+)44 整理得整理得 ,kjkkjikjijiC xC xC xG xC xa x 112120
29、01 kkkC xxC xC 110其中右端是次数不超过其中右端是次数不超过k-1次的多项式，设为次的多项式，设为P(x)。 ikkkiC xxxx1212,定义定义为为特征方程特征方程，它在复数域内刚好有，它在复数域内刚好有k个根，即个根，即其中其中k1+ki=k。这些根称为。这些根称为特征根特征根。这样，等式左边的函数可以表示为：这样，等式左边的函数可以表示为： ikkkixxx1212111,45 即即 ( )ikkkiP xG xxxx 1212111()()()().()()iikkkkikiikiiiAAAxxxAAAxxxAAAxxx 1122111122111221222222
30、12211111111146 (1) 如果所有特征根都互不相同，如果所有特征根都互不相同，则则( )kkAAAG xxxx1212111下面同样要根据特征根来进行分类讨论。下面同样要根据特征根来进行分类讨论。()()()nnnkknnnAxAxAx1122000(),nnnnkknAAAx 11220因此通项表达式为：因此通项表达式为：,nnnnkkaAAA1122其中常数其中常数A1, A2, , Ak可以利用初始条件来确定。可以利用初始条件来确定。47 (1) 如果有一对共轭复根如果有一对共轭复根(重数都为重数都为1)，重复以前的重复以前的讨论，不妨假设这一对共轭复根是讨论，不妨假设这一对
31、共轭复根是-,iiee12则则an的通项表达式中对应于的通项表达式中对应于的项为：的项为：AAxx 121211cossin,nnAnAn 12其中常数其中常数A1, A2和通项表达式中的其他常数一起由初和通项表达式中的其他常数一起由初始条件来决定。始条件来决定。48 (2) 如果有重根，如果有重根，不妨假设不妨假设 1 1是是m重根，则母函数中重根，则母函数中对应于对应于 1 1的项可以表示为的项可以表示为 mjjjAx 111因此通项表达式中对应于因此通项表达式中对应于 1 1的部分为：的部分为：.mnjjjnAn 111,mnnjnjjnAxn 1011注意到注意到C( j+n-1, n
32、)=C( j+n-1, j-1)是是n的的j-1次多项式，次多项式，因此这部分也可以表示为因此这部分也可以表示为 .mnmBB nBn 1011149 -,nnnddd 1220例例5 求下列求下列n阶行列式的值阶行列式的值dn：,xx2210特征方程为特征方程为,.dd1223.nd 21000121000121002 根据行列式的性质有：根据行列式的性质有：50 这是一个二重根，因此通项表达式可以设为：这是一个二重根，因此通项表达式可以设为： .nndABnABn1.rr121解得特征根为解得特征根为代入初始条件有代入初始条件有,dABdAB12223,.AB11因此因此n阶行列式的值为：
33、阶行列式的值为：.ndn151 -,nnnSSS1221例例6 计算计算Sn=1+2+n。显然有显然有 Sn-Sn-1=n，但这不是一个齐次递推关系。，但这不是一个齐次递推关系。注意到注意到 Sn-1-Sn-2=n-1，两式相减有，两式相减有再次利用再次利用 两式相减得两式相减得-,nnnSSS 12321-.nnnnSSSS 123330这是一个三阶线性常系数齐次递推关系。这是一个三阶线性常系数齐次递推关系。,xxx323310特征方程为特征方程为.rrr1231解得特征根为解得特征根为这是一个三重根，因此可以设这是一个三重根，因此可以设52 .nnSABnCnABnCn221代入初始条件有
34、代入初始条件有,SASABCSABC01201243,.ABC102因此有：因此有：().nnkSknnn n 21111122253 -,nnnSSSn12221例例7 计算计算Sn=12+22+n2。显然有显然有 Sn-Sn-1=n2， Sn-1-Sn-2=(n-1)2，两式相减有，两式相减有再次利用再次利用 两式相减得两式相减得-,nnnSSSn 123223-.nnnnSSSS 123332,xxxx43246410特征方程为特征方程为.rrrr12341解得特征根为解得特征根为这是一个四重根，因此可以设这是一个四重根，因此可以设再次利用再次利用 两式相减得两式相减得-,nnnnSSS
35、S1234332-.nnnnnSSSSS1234464054 .nSABnCnDn23代入初始条件有代入初始条件有,SASABCDSABCDSABCD0123012485392714,.ABCD1110623因此有：因此有：()().nnkn nnSknnn 23211111 21326655 -,nnnnnaaaaa123425840例例8 求解递推关系：求解递推关系：,xxxx43225840特征方程为特征方程为因此通项表达式可以设为：因此通项表达式可以设为：()cossin.nnnnnaABnCD1222,.aaaa 01235436,rrri 123 412解得特征根为解得特征根为ex
36、p.i 2256 代入初始条件有代入初始条件有,.aACaABDaABCaABD 0123524243386,.ABCD 3120因此通项表达式为：因此通项表达式为：cos.nnnan 1232()cossinnnnnnaABnCD122257 2.7 线性常系数非齐次递推关系线性常系数非齐次递推关系对于一个对于一个k阶线性常系数非齐次递推关系：阶线性常系数非齐次递推关系：( ),nnnkn kaC aC aC ab n1122与一般的线性问题类似，它的通解可以表示为特解与一般的线性问题类似，它的通解可以表示为特解与对应的齐次问题通解的和，即与对应的齐次问题通解的和，即*,nnnaaa其中其中
37、an*是非齐次递推关系的一个特解，而是非齐次递推关系的一个特解，而an是对应是对应的齐次递推关系的齐次递推关系nnnkn kaC aC aC a11220的通解。的通解。58 关于齐次递推关系的通解，我们已经讨论完全了。关于齐次递推关系的通解，我们已经讨论完全了。因此关键在于如何得到非齐次递推关系的因此关键在于如何得到非齐次递推关系的一个特解一个特解。下面我们针对一些特殊的右端项来讨论如何得到特下面我们针对一些特殊的右端项来讨论如何得到特解。解。-nnnaaan212563例例10 求递推关系：求递推关系：的一个特解。的一个特解。假设有如下形式的特解假设有如下形式的特解*.naAnBnC2代入
38、原递推关系，并整理后可得代入原递推关系，并整理后可得59 (-)(-).AnAB nABCn221234122917123因此有因此有因此可以得到一个特解因此可以得到一个特解*.nann 2117115424288,-,AABABC 123341202917120,.ABC117115424288解得解得60 (1) 一般来说，当右端项一般来说，当右端项b(n)是是n的的k次多项式时，特次多项式时，特解形式也可以设为解形式也可以设为k次多项式次多项式，即，即其中系数其中系数Ai由代入非齐次递推关系后确定。由代入非齐次递推关系后确定。*,knkaA nA nA10-nnaan17例例11 求递推
39、关系求递推关系 的一个特解。的一个特解。 假设有如下形式的特解假设有如下形式的特解*.naAnB代入原递推关系，并整理后易有代入原递推关系，并整理后易有.An 7但这是但这是不可能不可能的！的！61 问题出在当问题出在当1是原递推关系的特征根时，若把特解是原递推关系的特征根时，若把特解设为多项式，代入递推关系后，最高次会被消去。设为多项式，代入递推关系后，最高次会被消去。回到上例，因此回到上例，因此1是一重特征根，因此特解设为是一重特征根，因此特解设为*().nan AnB代入原递推关系，并整理后可得代入原递推关系，并整理后可得(2) 当右端项当右端项b(n)是是n的的k次多项式时，若次多项式
40、时，若1是递推关是递推关系的系的t重特征根，则特解的次数要提高重特征根，则特解的次数要提高t次次，即，即 *.tknkanA nA nA10.AnBAn27易有易有A=B=7/2，即一个特解为：，即一个特解为：*().nan n71262 -nnnnaaa125642 4例例12 求递推关系：求递推关系：的一个特解。的一个特解。假设有如下形式的特解假设有如下形式的特解*.nnaA4代入原递推关系有代入原递推关系有,nnnnAAA124546442 4化简得化简得42A=4216，即，即A=16。因此可以得到一个特解因此可以得到一个特解*.nnna 216 4463 -nnnnaaa12562例
41、例13 求递推关系：求递推关系：的一个特解。的一个特解。注意到注意到2是递推关系的一个特征根，因此是递推关系的一个特征根，因此2n是对应齐是对应齐次递推关系的解，即若把特解设为次递推关系的解，即若把特解设为A2n，则代入，则代入递推关系后，左端为递推关系后，左端为0，无法解出，无法解出A。*.nnaAn2代入原递推关系有代入原递推关系有()(),nnnnAnA nA n1225126222化简求得化简求得A=-2。因此可以得到一个特解因此可以得到一个特解*.nnnann 1222因此可以设特解形式为：因此可以设特解形式为：64 (3) 当右端项当右端项b(n)是常数乘以是常数乘以sn的形式时，
42、若的形式时，若s是递推是递推关系的关系的t重特征根，则特解形式可以设为重特征根，则特解形式可以设为其中系数其中系数A由代入非齐次递推关系后确定。由代入非齐次递推关系后确定。*,tnnaAn s 注意这包含了注意这包含了s不是特征根的情形，即不是特征根的情形，即t=0.把上面三种情况综合在一起，我们有下面的结论：把上面三种情况综合在一起，我们有下面的结论：若右端项若右端项b(n)=f(n)sn，其中，其中f(n)是是n的的k次多项式，次多项式，s是递推关系的是递推关系的t(t=0,1,2,)重特征根，则特解形式可重特征根，则特解形式可以设为以设为 *.tnknkan sA nA nA1065 -
43、()nnnnaaan 123107例例14 求递推关系：求递推关系：的通解。的通解。显然特征根为显然特征根为-5,2，-7不是特征根，因此特解可设为不是特征根，因此特解可设为*() ().nnaA nA 107代入原递推关系解得代入原递推关系解得,.AA 1049 182009 324注意到对应齐次递推关系的通解为注意到对应齐次递推关系的通解为A(-5)n+B2n，因，因此原递推关系的通解为此原递推关系的通解为其中其中A,B由初始条件确定。由初始条件确定。()(),nnnnAaBn 4920095271832466 -()nnnnaaan1231025例例15 求递推关系：求递推关系：的通解。
44、的通解。显然特征根为显然特征根为-5，2，2是是1重根，因此特解可以设为重根，因此特解可以设为*().nnan A nA102代入原递推关系解得代入原递推关系解得,.AA101 787 49注意到对应齐次递推关系的通解为注意到对应齐次递推关系的通解为A(-5)n+B2n，因，因此原递推关系的通解为此原递推关系的通解为其中其中A,B由初始条件确定。由初始条件确定。(),nnnnABnna 218752274967 例例16 求求Sn=12+22+n2。显然显然Sn满足满足Sn-Sn-1=n2，这是一个非齐次递推关系。，这是一个非齐次递推关系。由于由于1是递归关系的是递归关系的1重特征根，因此在设
45、特解时需重特征根，因此在设特解时需要把右端非齐次项中的多项式次数提高一次，即设要把右端非齐次项中的多项式次数提高一次，即设*().nSn A nA nA2210另一方面，对应齐次递推关系的通解为常数，因此另一方面，对应齐次递推关系的通解为常数，因此Sn应该是一个应该是一个三次多项式三次多项式，即可设为，即可设为常数常数A, B, C, D代入初始条件即可确定。代入初始条件即可确定。( , )( , )( , ).nSA C nB C nC C nD321同样的技巧可以用来计算同样的技巧可以用来计算Sn=13+23+n3等。等。68 叠加原理叠加原理：设右端项：设右端项b(n)有如下形式：有如下
46、形式：则非齐次递推关系的一个特解为则非齐次递推关系的一个特解为( )( ),miib nb n 1其中其中ai是右端项为是右端项为bi(n)时对应的特解。时对应的特解。*,mniiaa 1-nnnnnaaa125642 42例例17 求递推关系：求递推关系：的一个特解。的一个特解。根据叠加原理，问题变为求当右端项分别为根据叠加原理，问题变为求当右端项分别为424n和和2n时的特解，而这前面已经计算过了。因此特解为时的特解，而这前面已经计算过了。因此特解为*.nnnan214269 2.8 整数的拆分整数的拆分所谓正整数拆分即把正整数分解成若干正整数的和。所谓正整数拆分即把正整数分解成若干正整数
47、的和。相当于把相当于把n个无区别的球放到个无区别的球放到n个无标志的盒子，盒个无标志的盒子，盒子允许空着，也允许放多于一个球。子允许空着，也允许放多于一个球。整数拆分成若干整数的和，办法不一，不同拆分法整数拆分成若干整数的和，办法不一，不同拆分法的总数叫做拆分数。的总数叫做拆分数。拆分可以分为拆分可以分为无序拆分无序拆分和和有序拆分有序拆分；不允许重复的不允许重复的拆分拆分和和允许重复的拆分允许重复的拆分。70 例例9 若有若有1克、克、2克、克、3克、克、4克的砝码各一枚，问能克的砝码各一枚，问能称出那几种重量？有几种可能方案？称出那几种重量？有几种可能方案？()()()()xxxx2341
48、111.xxxxxxxxxx2345678910122222从右端的母函数知可称出从从右端的母函数知可称出从1克到克到10克，系数便是克，系数便是方案数。方案数。例如右端有例如右端有2x5项，即称出项，即称出5克的方案有克的方案有2种：种：5=2+3=1+4。类似的，称出类似的，称出6克的方案也有克的方案也有2种：种：6=2+4=1+2+3。71 例例10 求用求用1分、分、2分、分、3分的邮票贴出不同数值的方分的邮票贴出不同数值的方案数。案数。()()()xxxxxx22436111以以x4为例，其系数为为例，其系数为4，即，即4拆分成拆分成1，2，3之和的允之和的允许重复的拆分数为许重复的
49、拆分数为4：4 = 1+1+1+1 = 1+1+2 = 1+3 = 2+2。注意邮票允许重复，因此母函数为：注意邮票允许重复，因此母函数为：72 例例11 若有若有1克砝码克砝码3枚、枚、2克砝码克砝码4枚、枚、4克砝码克砝码2枚，枚，问能称出那几种质量？各有几种方案？问能称出那几种质量？各有几种方案？G xxxxxxxxxx23246848( )(1)(1)(1)即可称出即可称出1至至19克的质量，不同的方案数即为对应项克的质量，不同的方案数即为对应项前面的系数。前面的系数。母函数为：母函数为：xxxxxxxxxxxxxxxxxxx2345678910111213141516171819 1
50、223344 555544 3322.73 例例12 把整数把整数N无序拆分成整数无序拆分成整数a1,a2,an的和，且不的和，且不允许重复，求不同的拆分数。允许重复，求不同的拆分数。的不同解的个数。的不同解的个数。这个问题对应于求不定方程这个问题对应于求不定方程 ., , , ,. ,nnia xa xa xNxin11220 11 2令令bN表示不同的拆分数，则其对应的母函数为：表示不同的拆分数，则其对应的母函数为：( )()().().naaaG xxxx12111特殊的，当特殊的，当ai=i时，对应的母函数为：时，对应的母函数为：( )()().().nG xxxx211174 例例1
