復(fù)旦大學(xué)計(jì)算機(jī)科學(xué)與工程系吳永輝離散數(shù)學(xué)生成函數(shù)與遞推關(guān)系

第十二章生成函數(shù)與遞推關(guān)系12.1冪級數(shù)型生成函數(shù)（多重集的組合）

12.2指數(shù)型生成函數(shù)（多重集的排列）

12.3遞推關(guān)系引言1.生成函數(shù)(母函數(shù))生成函數(shù)(稱為母函數(shù))是組合數(shù)學(xué)中的一個重要內(nèi)容，可用來求解組合計(jì)數(shù)問題。1)例:(1+a1x)(1+a2x)……(1+anx)=1+(a1+a2+……+an)x+(a1a2+a1a3+……+an-1an)x2+……+a1a2……anxnx的系數(shù)為a1+a2+……+an;/*包含從{a1,a2,……,an}中取一個組合的全體*/x2的系數(shù)為a1a2+a1a3+……+an-1an;

/*包含從{a1,a2,……,an}中取兩個組合的全體*/x3的系數(shù)為a1a2a3+a1a2a4+……+an-2an-1an;/*包含從{a1,a2,……,an}中取三個組合的全體*/…………xn的系數(shù)為a1a2……an;/*包含從{a1,a2,……,an}中取n個組合的全體*/若令a1=a2=……=an=1,則(1+x)n=1+C(n,1)x+C(n,2)x2+……+C(n,n)xn(1+x)n=C(n,k)：從{a1,a2,……,an}中取k個的組合數(shù)。2)例：(1+x)m(1+x)n=(1+x)m+n左式=[C(m,0)+C(m,1)x+……+C(m,m)xm]

[C(n,0)+C(n,1)x+……+C(n,n)xn]右式=[C(m+n,0)+C(m+n,1)x+……+C(m+n,m+n)xm+n]展開左式，得：C(m,0)

C(n,0)+[C(m,1)

C(n,0)+C(m,0)

C(n,1)]x+[C(m,2)

C(n,0)+C(m,1)

C(n,1)+C(m,0)

C(n,2)]x2+……+C(m,m)

C(n,n)xm+n比較對應(yīng)項(xiàng)的系數(shù)，得：C(m+n,1)=C(m,1)

C(n,0)+C(m,0)

C(n,1)C(m+n,2)=C(m,2)

C(n,0)+C(m,1)

C(n,1)+C(m,0)

C(n,2)……………一般有：C(m+n,r)=C(m,0)C(n,r)+C(m,1)C(n,r-1)+……+C(m,r)C(n,0)/*Vandermonde恒等式*/2.生成函數(shù)(母函數(shù))的定義對于序列a0,

a1,a2,……，定義a0+a1x+a2x2+……為序列a0,

a1,a2,……的生成函數(shù)(母函數(shù))。例如：(1+x)n是C(n,0),C(n,1),C(n,2),……,C(n,n)的生成函數(shù)(母函數(shù))。3.生成函數(shù)(母函數(shù))的實(shí)例有紅球兩只，白球、黃球各一只，有多少種不同的組合方案？設(shè)r,w,y分別代表紅球，白球和黃球。解題思想：紅球不?。╮0=1），取1只（r1=r），取2只（r2）；黃球不?。▂0=1），取1只（y1=y），白球不?。╳0=1），取1只（w1=w），根據(jù)乘法原理：(1+r+r2)(1+w)(1+y)=1+(r+w+y)+(r2+ry+rw+yw)+(r2y+r2w+rwy)+r2yw取一個球的組合數(shù)為3：r，w，y取兩個球的組合數(shù)為4：r2，ry，rw，yw取三個球的組合數(shù)為3：r2y，r2w，rwy取四個球的組合數(shù)為1：r2yw

許多組合學(xué)計(jì)數(shù)問題依賴于一個整數(shù)參數(shù)n。這個參數(shù)n常常表示問題中某個基本集或多重集的大小、組合的大小、排列中的位置等。因此一個計(jì)數(shù)問題常常不是一個孤立的問題而是一系列的單個問題。例：令hn表示{1,2,…,n}的排列數(shù)。hn=n!，于是得到數(shù)列h0,h1,h2,…,hn,

…。對于這個數(shù)列，一般項(xiàng)hn=n!，通過選擇n為一個特定的整數(shù)可以得到這個問題的一個實(shí)例。如：h5=5!。

一個整數(shù)參數(shù)的某些計(jì)數(shù)問題的代數(shù)求解方法，或者導(dǎo)致一個顯式公式，或者歸結(jié)為一個函數(shù)，即生成函數(shù)，它的冪級數(shù)的系數(shù)給出計(jì)數(shù)問題的解。12.1冪級數(shù)型生成函數(shù)一、實(shí)例二、生成函數(shù)的定義三、形式冪級數(shù)的運(yùn)算性質(zhì)四、用生成函數(shù)來求多重集的r-組合數(shù)一、實(shí)例11章提到：求多重集S={n1·a1,n2·a2,…,nk·ak}

(n=n1+n2+…+nk)的r-組合數(shù)時，當(dāng)對一切i=1,2,…,k有ni

r時，有計(jì)算公式N=C(k+r-1,r)；而當(dāng)r<n，且存在某個ni<r,利用容斥原理予以解決。

利用組合模型來模擬多重集的r-組合數(shù)。例：設(shè)有n個標(biāo)志為1,2,…,n的網(wǎng)袋，第i個(i=1,2,…n)網(wǎng)袋里放有ni個球。不同網(wǎng)袋里的球是不同的，而同一網(wǎng)袋里的球則是沒有差別的，認(rèn)為是相同的。

多重集S的一個6-組合a1a1a3a3a3a4就相應(yīng)于從第1個網(wǎng)袋里取2個球，第3個網(wǎng)袋里取3個球，第4個網(wǎng)袋里取1個球。從第1個網(wǎng)袋里取2個球，第3個網(wǎng)袋里取3個球，第4個網(wǎng)袋里取1個球。就對應(yīng)了S的一個6-組合a1a1a3a3a3a4。

多重集S的r-組合數(shù)就等于從n個網(wǎng)袋里取r個球的取法數(shù)。用x代表球，xi1代表從第1個網(wǎng)袋里取i1個球，xi2代表從第2個網(wǎng)袋里取i2個球，…,xik代表從第k個網(wǎng)袋里取ik個球。i1,i2,…,ik個滿足條件i1+i2+…+ik=r(ij

nj,j=1,2,…,k)。故xi1xi2…xik=xi1+i2+…+ik=xr就對應(yīng)了多重集S的一個r-組合。因?yàn)榻o出1個xr的構(gòu)成就等于給出了多重集S的一個r-組合，所以xr的系數(shù)就是多重集S的r-組合數(shù)。利用上述方法就得到了求組合數(shù)的方法，就稱為生成函數(shù)法。二、生成函數(shù)的定義定義12.1：設(shè)a0,a1,…,an,…是一個數(shù)列，構(gòu)造形式冪級數(shù)f(x)=a0+a1x+a2x2+…+anxn+…,稱f(x)是數(shù)列a0,a1,…,an,…的生成函數(shù)，且兩個形式冪級數(shù)相等當(dāng)且僅當(dāng)對每個i，有ai=bi。

對于有限序列，可看成自某項(xiàng)后全為

0的無窮序列。

為什么稱為形式冪級數(shù)？

根據(jù)高等數(shù)學(xué)，作為冪級數(shù)要討論它們的收斂范圍，即當(dāng)x在收斂范圍內(nèi)取值時，冪級數(shù)才會收斂于某個函數(shù)f(x)。而這里，x僅是記號，并不需要賦值，從而也不需要考慮收斂范圍，故稱為形式冪級數(shù)，而x也稱為形式變元。

三、形式冪級數(shù)的運(yùn)算性質(zhì)定理12.1：設(shè)數(shù)列{an},{bn},{cn}的生成函數(shù)分別是f(x),g(x)和h(x)，r為常數(shù)。(1)如果bn=ran，則g(x)=rf(x)。(2)如果cn=an+bn，則h(x)=f(x)+g(x)。(3)如果則h(x)=f(x)*g(x)。(6)如果則(8)如果bn=rnan，則g(x)=f(rx)。(9)如果bn=nan，則g(x)=xf'(x)。/*證明思想：定義12.1*/例12.1(1)設(shè)有質(zhì)量分別為n1克，n2克，…,nk克的k個砝碼?，F(xiàn)要用天平稱i克的物體，物體放在左邊，砝碼放在右邊，共有多少種不同稱法?(2)用質(zhì)量分別為1克，2克，4克，8克，16克的5個砝碼，在天平上能稱幾種質(zhì)量的物體？每種質(zhì)量的物體有幾種不同的稱法?(3)用2個質(zhì)量為1克，3個質(zhì)量為2克，2個質(zhì)量為5克的砝碼在天平上能稱幾種質(zhì)量的物體?且每種質(zhì)量的物體有幾種不同的稱法?解：(1)

設(shè)有ai種方法稱i克物體。K個形式冪集數(shù)的積為(1+xn1)(1+xn2)……(1+xnk)。該展開式中的xi冪來源于xm1xm2…xmk=xi，m1+m2+…+mk=i,mj

{0,nj}。其中第一個括弧提供m1次冪，第二個括弧提供m2次冪，…，第k個括弧提供mk次冪，mj=0(x0=1)表示nj克砝碼沒有用上，mj=nj表示nj克砝碼用上了，因此展開式中xi的系數(shù)恰好是稱i克物體的方法數(shù)，故有：(2)設(shè)質(zhì)量r克物體有ar種稱法，則數(shù)列{ar}的生成函數(shù)是f(x)=(1+x)(1+x2)(1+x4)(1+x8)(1+x16),/*1+x表示砝碼為1克的或者不取或者取,取了就是1克,1+x16表示砝碼為16克的或者不取或者取,取了就是16克*/

(1-x)f(x)=(1-x)(1+x)(1+x2)(1+x4)(1+x8)(1+x16)=1-x32。所以f(x)=(1-x32)/(1-x)=1+x+x2+…+x31。因?yàn)閤i前面系數(shù)都是1，這表明凡是不超過

31克的物體都能用給定的

5個砝碼稱出，且每個恰有一種稱法。(3)設(shè)質(zhì)量r克物體有ar種稱法，則數(shù)列{ar}的生成函數(shù)是f(x)=(1+x+x2)(1+x2+(x2)2+(x2)3)(1+x5+(x5)2)）/*1+x+x2表示2個質(zhì)量為1克的砝碼或者不用(x0=1)，或者用1個(x1=x)，或者用2個(x2)*/=1+x+2x2+x3+2x4+2x5+3x6+3x7+2x8+2x9+2x10+3x11+3x12+2x13+2x14+x15+2x16+x17+x18。/*表明凡是質(zhì)量不超過

18克的物體都能用給定的砝碼稱出。其中質(zhì)量為

1,3,15,17,18克的只有一種稱法，質(zhì)量為

2,4,5,8,9,10,13,14,16克的物體有2種稱法，而質(zhì)量為

6,7,11,12克的物體有3種稱法。*/

四、用生成函數(shù)來求多重集的r-組合數(shù)例12.2：設(shè)多重集S={

·a1,

·a2,…,

·ak}，S的r-組合數(shù)是ar=C(r+k-1,r)，它也是方程x1+x2+…+xk=r的非負(fù)整數(shù)解的個數(shù)?，F(xiàn)用生成函數(shù)的方法求ar。

設(shè){ar}的生成函數(shù)為f(y)，構(gòu)造冪級數(shù)(1+y+y2+…)k/*(1+y+y2+…)表示ai可以不取,取1個,2個…*/

展開該式，yr冪來源于yx1yx2…yxk=yx1+x2+…+xk,x1+x2+…+xk=r，其中yx1來自第一個因式(1+y+y2+…)，yx2來自第二個因式(1+y+y2+…)，…，yxk來自第k個因式(1+y+y2+…)，且x1,x2,…,xk為非負(fù)整數(shù)。因此展開式中yr的系數(shù)對應(yīng)了不定方程x1+x2+…+xk=r的非負(fù)整數(shù)解的個數(shù)。故所構(gòu)造的冪級數(shù)就是{ar}的生成函數(shù)f(y)。由推論11.4可得:所以ar=C(k+r-1,r)

設(shè)多重集S={n1·a1,n2·a2,…,nk·ak}，S的r-組合數(shù)ar就相當(dāng)于方程x1+x2+…+xk=r(x1

n1,x2

n2,…,xk

nk)的非負(fù)整數(shù)解的組數(shù)。設(shè){ar}的生成函數(shù)為f(y)，類似可以得到：f(y)=(1+y+y2+…+yn1)(1+y+y2+…+yn2)…(1+y+y2+…+ynk)，則

f(y)的展開式中yr的系數(shù)ar就是所求的S的r-組合數(shù)。

例12.3:設(shè)S={

·a1,

·a2,…,

·ak}，求S的每個元素只出現(xiàn)偶數(shù)次的r-組合數(shù)ar。解：令{ar}的生成函數(shù)是f(y)，因?yàn)橐骃的每個元素只出現(xiàn)偶數(shù)次，則對a1來講，或者不出現(xiàn)，或者是2，4，6，…其他也類似。故生成函數(shù)為：

f(y)=(1+y2+y4+…)k=1/(1-y2)k=1+ky2+C(k+1,2)y4+…+C(k+n-1,n)y2n+…

所以有例12.4：求x1+x2+x3=5(0

x1,0

x2,1

x3)的整數(shù)解組數(shù)。解：令x3’=x3-1，則原問題即為求在約束條件0

x1,0

x2,0

x3’下x1+x2+x3’=4的非負(fù)整數(shù)解組數(shù)。解的組數(shù)為a4,{ar}的生成函數(shù)是所以有a4=C(4+2,4)=15。

12.2指數(shù)型生成函數(shù)1.問題提出：用生成函數(shù)解決排列問題

a1,

,an互不相同，n個元素a1,

,an的全排列：n！。如果其中a1重復(fù)n1次，全排列：n!/n1!。如果其中a1重復(fù)n1次，a2重復(fù)n2次，……，如果其中ah重復(fù)nh次，n1+n2+……+nh=n;全排列：例：8個元素中a1重復(fù)3次，a2重復(fù)2次，a3重復(fù)3次，從中取r個組合。解：(1+x1+x12+x13)(1+x2+x22)(1+x3+x32+x33)=[1+(x1+x2)+(x12+x1x2+x22)+(x13+x12x2+x1x22)+(x13x2+x12x22)+x13x22](1+x3+x32+x33)展開式中4次方項(xiàng)為:x1x33+x2x33+x12x32+x1x2x32+x22x32+x13x3+x12x2x3+x1x22x3+x13x2+x12x22x1x33項(xiàng)表示1個a1,3個a3;x1x22x3項(xiàng)表示1個a1,2個a2,1個a3;x1x33對應(yīng)的排列數(shù)為4!/1!3!,x1x22x3對應(yīng)的排列數(shù)為4!/1!2!1!.取4個元素的排列數(shù)為:指數(shù)型生成函數(shù):取4個的排列數(shù)為取5個的排列數(shù)為2.定義12.2:設(shè)a0,a1,

,an,

是一個數(shù)列，構(gòu)造形式冪級數(shù)稱f(x)是數(shù)列a0,a1,

,an,

的指數(shù)型生成函數(shù)。

定理12.2：設(shè)an,bn的指數(shù)生成函數(shù)分別為fe(x)和ge(x)，則：其中

例：數(shù)列1,1,……,1,……的指數(shù)型生成函數(shù)為:3.指數(shù)型生成函數(shù)來解決多重集的排列問題定理12.3：設(shè)有限多重集S={n1·a1,n2·a2,…,nk·ak}，且n=n1+n2+…+nk，對任意的非負(fù)整數(shù)r，

r為S的r-排列數(shù)，則數(shù)列

r的指數(shù)型生成函數(shù)為：g(x)=gn1(x)·gn2(x)·…·gnk(x)，其中g(shù)ni(x)=1+x+x2/2!+…+xni/ni!,i=1,2,…,k。

證明思想：要證明

r的指數(shù)型生成函數(shù)為gn1(x)·gn2(x)·…·gnk(x)，關(guān)鍵是證明gn1(x)·gn2(x)·…·gnk(x)的展開式中項(xiàng)xr/r!的系數(shù)就是

r。

證明：/*考察gn1(x)·gn2(x)·…·gnk(x)的展開式中項(xiàng)xr/r!的情況。*/

xr的項(xiàng)為下述項(xiàng)之和其中m1+m2+……+mk=r,0mini,i=1,2,…,k.上式可以寫成:所以在g(x)的展開式中的系數(shù)是:這里求和是對方程m1+m2+……+mk=r,0mini,(i=1,2,…,k.)的一切非負(fù)整數(shù)解進(jìn)行求和的。又因?yàn)閷潭ǖ膍1，m2，……，mk，就是S的r元子集{m1·x1,m2·x2,…,mk·xk}的全排列數(shù)。故ar就是S的所有r元子集的全排列數(shù)之和，即S的r-排列數(shù)。所以g(x)的展開式中的的系數(shù)ar就是多重集S的r-排列數(shù)。例12.5：設(shè)有6個數(shù)字，其中

3個數(shù)字

1,2個數(shù)字6,1個數(shù)字8，問能組成多少個四位數(shù)?解：這實(shí)際上是求S={3·x1,2·x2,1·x3}中取4個的多重集排列數(shù)問題。其指數(shù)型生成函數(shù)為：g(x)=(1+x+x2/2!+x3/3!)(1+x+x2/2!)(1+x)=1+3x+8(x2/2!)+19(x3/3!)+38(x4/4!)+60(x5/5!)+60(x6/6!)由此可得a4=38，即可組成38個四位數(shù)。

泰勒級數(shù)例：求1，3，5，7，9這5個數(shù)字組成的n位數(shù)個數(shù)，要求其中3和7出現(xiàn)的次數(shù)為偶數(shù)，其他數(shù)字出現(xiàn)的次數(shù)無限制。解：12.3遞推關(guān)系1.遞推綜述遞推關(guān)系是離散變量之間變化規(guī)律中常見的一種方式，與生成函數(shù)一樣是解決計(jì)數(shù)問題的有力工具。對數(shù)列{un},如從某項(xiàng)后，un前k項(xiàng)可推出un的普遍規(guī)律，就稱為遞推關(guān)系。利用遞推關(guān)系和初值在某些情況下可以求出序列的通項(xiàng)表達(dá)式un，稱為該遞推關(guān)系的解。2.遞推關(guān)系實(shí)例1)例12.6：13世紀(jì)初意大利數(shù)學(xué)家

Fibonacci研究過著名的兔子繁殖數(shù)目問題:設(shè)一對一雌一雄小兔剛滿2個月時，便可繁殖出一雌一雄一對小兔。以后每隔1個月生一對一雌一雄小兔。由一對剛出生的小兔開始飼養(yǎng)到第n個月，有多少對兔子?解：設(shè)第n個月有Fn對兔子，它由兩部分組成:(1)新生出的小兔，其數(shù)目等于能生小兔的大兔對數(shù)目，由于小兔滿兩個月才能繁殖，故數(shù)目為第(n-2)個月時的兔對數(shù)目，即為Fn-2。(2)原有小兔，其數(shù)目等于上月(即第

n-1個月)的兔對數(shù)目，即為Fn-1。因此可建立如下的遞推關(guān)系:Fn=Fn-2+Fn-1，并有初始條件：F1=F2=1。即這是一個帶有初值的遞推關(guān)系。/*滿足這種遞推關(guān)系的數(shù)列稱為Fibonacci數(shù)列*/

2)例12.7：設(shè)多重集S={

·a,

·b,

·c}，求a不相鄰的n-排列數(shù)。

解:設(shè)a不相鄰的n-排列數(shù)為an。則a1=3,a2=32-1=8/*減1是為了減去aa*/當(dāng)n≥3時，a不相鄰的所有n-排列可分為互不相容的兩類:(1)第一個位置排b或c，剩下的n-1個位置a不相鄰，由an的定義知，a不相鄰的(n-1)-排列數(shù)為an-1，根據(jù)乘法原則，這類排列數(shù)為2an-1。(2)第一個位置排a，則第二個位置只能排b或c，而剩下的n-2個位置a不相鄰，由an的定義知，a不相鄰的(n-2)-排列數(shù)為an-2，根據(jù)乘法原則，這類排列數(shù)為2an-2。由加法原則知，a不相鄰的n-排列數(shù)為:an=2an-1+2an-2，并有初始條件:a1=3,a2=8,即這是一個帶有初值的遞推關(guān)系。

思想總結(jié)：分而治之3.兩種求解遞推關(guān)系的方法1)求解常系數(shù)線性遞推關(guān)系的特征根方法

（1）定義12.3

數(shù)列{an}滿足遞推關(guān)系an=h1an-1+h2an-2+…+hkan-k,hi為常數(shù)，i=1,2,…,k,n≥k,hk≠0，稱該遞推關(guān)系為an的k階常系數(shù)線性齊次遞推關(guān)系。形如an=h1an-1+h2an-2+…+hkan-k+f(n),hi為常數(shù)，i=1,2,…,k,n≥k,hk≠0，稱該遞推關(guān)系為an的k階常系數(shù)線性非齊次遞推關(guān)系。k階常系數(shù)線性齊次遞推關(guān)系與微分方程y(k)=h1y(k-1)+h2y(k-2)+…+hky，hi為常數(shù)（i=1,2,…,k,）在結(jié)構(gòu)上類似；

k階常系數(shù)線性非齊次遞推關(guān)系與微分方程y(k)=h1y(k-1)+h2y(k-2)+…+hky+f(n)，hi為常數(shù),(i=1,2,…,k)在結(jié)構(gòu)上也類似；求解方法也與相應(yīng)的微分方程類似。（2）求解方法求解常系數(shù)線性遞推關(guān)系的基本方法是尋找形如an=rn的解。

an=rn是an=h1an-1+h2an-2+…+hkan-k的解，rn=h1rn-1+h2rn-2+……+hkrn-k的等價方程rk-h1rk-1-h2rk-2-……-hk=0。這個方程稱為該遞推關(guān)系的特征方程，方程的解稱為該遞推關(guān)系的特征根。（3）定義12.4:

方程xk-h1xk-1-h2xk-2-…-hk=0稱為k階常系數(shù)線性齊次遞推關(guān)系的特征方程,它的k個根q1,q2,…,qk稱為該遞推關(guān)系的特征根。其中qi(i=1,2,…,k)是復(fù)數(shù)。定理12.4.

an=qn,q≠0是常系數(shù)線性齊次遞推關(guān)系的解的充要條件是:q是該遞推關(guān)系的特征根。

定理12.5:

若k階常系數(shù)線性齊次遞推關(guān)系的特征方程有k個互異的特征根:q1,q2,…,qk，則該遞推關(guān)系的通解為:an=c1q1n+c2q2n+…+ckqkn,其中c1,c2,…ck為任意常數(shù)。例12.8求例12.7的帶初值遞推關(guān)系的解。解：例12.7的遞推關(guān)系的特征方程為：x2-2x-2=0,其根為：由定理12.5，遞推關(guān)系的通解為：要滿足初值條件，故有：所以，a不相鄰的n-排列數(shù)為:定理12.6:若k階常系數(shù)線性齊次遞推關(guān)系的特征方程有t個互異的特征根:q1,q2,…,qt，m1,m2,…,mt為相應(yīng)根的重?cái)?shù)，且m1+m2+…+mt=k,

則該遞推關(guān)系的通解為:

其中cij為任意常數(shù)(1≤j≤mi,1≤i≤t)為任意常數(shù)。

例12.9求解遞推關(guān)系an+an-1-3an-2-5an-3-2an-4=0,n

4a0=1,a1=a2=0,a3=2解:該遞推關(guān)系的特征方程是x4+x3-3x2-5x-2=0,其特征根是-1,-1,-1,2。由定理12.6得：an=c11(-1)n+c12n(-1)n+c13n2(-1)n+c212n代入初值得到以下方程組：

c11+c21=1-c11-c12-c13+c21=0c11+2c12+4c13+4c21=0-c11-3c12-9c13+8c21=2解此方程組得：c1=7/9,c2=-13/16,c3=1/16,c4=1/8故遞推關(guān)系的解是：an=7/9(-1)n-(13/16)n(-1)n+(1/16)n2(-1)n+(1/8)2n

(4)k階常系數(shù)線性非齊次遞推關(guān)系

k階常系數(shù)線性非齊次遞推關(guān)系的通解與k階常系數(shù)線性非齊次微分方程的通解類似,也是齊次通解與特解之和，即：an=a'n+an*

其中a'n是k階常系數(shù)線性非齊次遞推關(guān)系所對應(yīng)的k階常系數(shù)線性齊次遞推關(guān)系an=h1an-1+h2an-2+…+hkan-k=0的通解，而an*是k階常系數(shù)線性非齊次遞推關(guān)系的特解。求解方法對于a'n由定理12.6即得，故關(guān)鍵是an*的求解。對于一般的f(n)沒有普遍的解法，在某些簡單的情況下可用待定系數(shù)法求出an*。(1)當(dāng)f(n)是n的t次多項(xiàng)式時，對應(yīng)的特解形式為：

an*=P1nt+P2nt-1+…+Ptn+Pt+1，其中P1,P2,…,Pt,Pt+1為待定系數(shù)。(2)當(dāng)f(n)是

n的形式時，若

不是對應(yīng)的齊次遞推關(guān)系的特征根，則對應(yīng)的特解是P?

n，其中P為待定系數(shù)；若

是對應(yīng)的齊次遞推關(guān)系的m重特征根，則對應(yīng)的特解是

P?nm?

n，其中P為待定系數(shù)。例12.10:

求解遞推關(guān)系an+2an-1=n+1,n

1,a0=2。解:該遞推關(guān)系導(dǎo)出的齊次線性遞推關(guān)系an+2an-1=0的特征方程是x+2=0，其特征根是-2。由定理12.5知其通解為a’n=c(-2)n；又因f(n)=n+1，故它的特解具有形式an*=P1n+P2，其中P1,P2為待定系數(shù)。將其代入原遞推關(guān)系P1n+P2+2(P1?(n-1)+P2)=n+1，即：3P1n+3P2-2P1=n+1，比較上式兩端n的同次冪的系數(shù)，得：P1=1/3,P2=5/9。因此，an*=(n/3)+5/9是原遞推關(guān)系的特解。而它的通解是an=c(-2)n+(n/3)+5/9。要它滿足初值，只須2=c+(5/9),

故c=13/9。所以帶初值的遞推關(guān)系的解為：an=(13/9)(-2)n+(n/3)+5/9

例:求h(n)=2h(n-1)+1,并有初始條件:h(1)=1的遞推關(guān)系解:特征根x=2,所以h'(n)=c2n,因?yàn)閒(n)=1,所以特解h*(n)=P1,代入原遞推關(guān)系P1=2P1+1,

所以P1=-1.因此h(n)=c2n-1.因?yàn)閔(1)=1,所以c=1.故h(n)=2n-1.例:求解下面遞推關(guān)系的特解an=an-1+7n,n

1.解:該遞推關(guān)系導(dǎo)出的齊次線性遞推關(guān)系an-an-1=0的特征方程是x-1=0，其特征根是1。因?yàn)閒(n)=7n，如果設(shè)特解為an*=P1n+P2,

代入原遞推關(guān)系P1n+P2-P1(n-1)-P2=7n，即：P1=7n，與P1為常量矛盾。其原因是當(dāng)唯一的特征根是1時,若所設(shè)特解中n最高次冪與f(n)一樣時,代入遞推關(guān)系后,等式左邊的n最高次冪比右邊的次數(shù)低,在此情況上,采用升冪的方法,且可不設(shè)常數(shù)項(xiàng).令an*=P1n2+P2n,

代入原遞推關(guān)系化簡后得:2P1n+P2-P1=7n，比較上式兩端n的同次冪的系數(shù)，得：2P1=7,P2-P1=0，所以P2=P1=7/2。因此，an*=7n/2+7/2

解：遞推關(guān)系：an=4an-1-5an-2+2an-3,n

3(*),特征方程x3-4x2+5x-2=0,特征根x1=x2=1,x3=2,通解：an=c1+c2*n+c3*2n,因?yàn)?是(*)的一重特征根，所以遞推關(guān)系an=4an-1-5an-2+2an-3+2n