遞歸關系

5.1幾個典型的遞歸關系實例

5.2常系數線性齊次遞歸關系的基本解法

5.3常系數線性非齊次遞歸關系的解法

5.4迭代法求解遞歸關系

5.5生成函數方法求解遞歸關系5.1幾個典型的遞歸關系實例

例1(錯排問題設S={1,2,…,n}，令D(n)為S上元素的錯排數，即n個元素都不在其自然位置上的排列數），則D(n)=(n-1)(D(n-2)+D(n-1)),n≥3,D(1)=0,D(2)=1

證明對于每個錯排，第一位上的數字只能取2,3,…,n中之一。以第一位數字的取法可將全部錯排分為n-1類:P2,P2,…,Pn

，即P2={(2,i2,i3,…,in)|it≠t,t=2,3,…,n}

P3={(3,j2,j3,…,jn)|jt≠t,t=2,3,…,n}

…

Pn={(n,k2,k3,…,kn)|kt≠t,t=2,3,…,n}易知|P2|=|P3|=…=|Pn|都是相同的，令其為dn，于是Dn=(n-1)·dn考察P2={(2,i2,i3,…,in)|it≠t,t=2,3,…,n}

將P2中的錯排按第二位上的數字取1或不取1分為兩類，分別記為P21,P2x：P21={(2,1,i3,…,in)|it≠t,t=3,4,…,n}

P2x={(2,i2,i3,…,in)|i2≠1,it≠t,t=3,4,…,n}顯見|P21|=D(n-2)

|P2x|=|{(i2,i3,…,in)|it+1≠t,t=1,2,…,n-1}|=D(n-1)從而dn=D(n-2)+D(n-1)，故知D(n)=(n-1)(D(n-2)+D(n-1)),n≥3,D(0)=0,D(2)=1

例2（Hanoi塔問題）n個圓盤，從A柱經B柱移到C柱(參見圖5.1.1)。要求每次只移一個圓盤；移動過程始終保持大盤在下，小盤在上；中途A、B、C柱均可作臨時柱，最終移至C柱，則A到C的最少移動次數為h(n)=2h(n-1)+1

圖5.1.1Hano塔示意圖

解設h(n)為問題的解，則h(1)=1,h(2)=3=2h(1)+1,h(3)=5=2h(2)+1,…,h(n)=2h(n-1)+1。又若設利用C柱把A柱上n-1個圓盤移到B柱，移動次數為h(n-1)，則將A柱所剩最大圓盤移到C柱只需移動一次，再將B上的n-1個圓盤利用A柱移到C柱（已有一個最大圓盤在下面）共需移動h(n-1)次。故總的移動次數為h(n)=2h(n-1)+1。

例3(Fibonacci問題)

(1)兔子問題:Fn+1=Fn+Fn-1,F0=F1=1,F2=2。

(2)棋盤用骨牌覆蓋問題(如圖5.1.2所示)。

(3)S={0,1}的n位符號串中不出現“11”的方案數。

(4)無相鄰整數的子集數。圖5.1.22×n棋盤用n枚1×2骨牌覆蓋示意圖

解

(1)兔子問題的遞歸關系在前面章節已得到。

(2)參見圖5.1.2（a）、(b)，求2×n棋盤用n枚1×2骨牌完全覆蓋的方案數。設Fn為問題的解，圖5.1.2（a）中豎著覆蓋1枚骨牌，剩余的為2×(n-1)格棋盤，有Fn-1種方案；圖5.1.2（b）中橫著覆蓋2枚骨牌，剩余2×(n-2)格棋盤，有Fn-2種方案。故Fn=Fn-1+Fn-2,n≥2

Fn+1=Fn+Fn-1,n≥1,F0=F1=1,F2=2圖5.1.3n×n方格不穿越對角線走法(3)S={0,1}，重復度為∞，求Ｓ的n位符號串中不出現“11”的串的數目。設Fn為問題的解，末位為0，滿足題設的n-1位串有Fn-1個；末位為1，最后兩位必為01，滿足題設的n-2位串有Fn-2個，故Fn=Fn-1+Fn-2,F1=1,F2=2

F0=1

(4)令S={1,2,…,n}，對T∈2S，構造函數f:2S→{0,1}n，f(T)=b1b2…bn，i=1,2,…,n，bi=1,i∈Tbi=

0,iT，從而，求無相鄰整數的子集問題轉化為求無“11”字樣的n位01串問題。

例4(Catalan問題)設Cn為問題的解，并設第一次碰到對角線的點為(k,k)，參見圖5.1.3，則從(0,0)到(k,k)的走法為Ck-1，又(k,k)點以后滿足題意的走法為Cn-k。由乘法原理得5.2常系數線性齊次遞歸關系的基本解法

定義若對n≥2，序列{an}滿足

an+c1an-1+c2an-2=0 (5.2.1)

a0=d0,a1=d1 (5.2.2)其中，c1,c2為常數，n≥2，c2≠0，d0，d1為實常數，則稱（5.2.1）式為關于序列{an}的二階常系數線性齊次遞歸關系，（5.2.2）式稱為初值條件。之所以稱為二階是因c2≠0，否則可考慮更低的階；稱為常系數是因an-2,an-1,an之前的c2,c1及c0=1都是常數；稱為線性是因an-2,an-1,an都是一次的；稱為齊次是因常數項為0。例如：an+2an-1=0 一階遞歸關系an+(n-2)an-1+an-2=0變系數遞歸關系an+3a2n-1+an-2=0非線性遞歸關系an-2an-1=1非齊次遞歸關系對x≠0，稱x2+c1x+c2=0 (5.2.3)為{an}的特征方程，（5.2.3）式的解稱為{an}的特征根。

（1）設（5.2.3）式有二不等實根：r1≠r2，則（5.2.1）式的通解為an=K1rn1+K2rn2其中K1,K2為可由初值確定的待定常數。（2）設（5.2.3）式的解為二相等實數：r1=r2=r，則（5.2.1）式的通解為an=(K1+nK2)rn

其中，K1,K2為待定常數。

（3）設（5.2.3）式的解為一對共軛復根：r1=α+βi=ρeiθ=ρ(cosθ+isinθ)

r2=α-βi=ρe-iθ=ρ(cosθ-isinθ)則（5.2.1）式的通解為an=K1rn1+K2rn2或 an=Aρncosnθ+Bρnsinnθ其中，A=K1+K2，B=(K1-K2)i為待定常數。α,β,ρ=(α2+β2)1/2

為實數，θ=arctan為輻角。

定理1（遞歸關系的解與特征方程的解之間的關系）對n≥2,r≠0,an=rn是遞歸關系an+c1an-1+c2an-2=0的解iffr是方程x2+c1x+c2=0的解。

證明對n≥2，r≠0，an=rn為an+c1an-1+c2an-2=0的解。

iff

rn

+c1rn-1+c2an-2=0

iff

r2+c1r+c2=0

iff

r是方程x2+c1x+c2=0的解。

定理2（解的迭加性）設an=rn1，an=rn2都是遞歸關系an+c1an-1+c2an-2=0的解，則K1rn1+K2rn2也是該遞歸關系的解。其中，K1,K2為任意常數。

證明

定理3設r1=r2=r≠0是方程x2+c1x+c2=0的重根，則an=rn和an=nrn都是遞歸關系an+c1an-1+c2an-2=0的解。

證明由定理1知，rn一定是遞歸關系an+c1an-1+c2an-2的解。現只需證an=nrn也是該遞歸關系的解即可。事實上，設r≠0是方程x2+c1x+c2=0的非零二重根，則r也一定是方程xn+c1xn-1+c2xn-2=0的非零二重根。從而r一定是方程

的解。這就證明了an=nrn是遞歸關系an+c1an-1+c2an-2=0的解。

定理4只要r1≠r2是方程x2+c1x+c2=0的二不同特征根，那么an=K1rn1+K2rn2一定是遞歸關系an+c1an-1+c2an-2=0的通解。其中K1,K2為任意實數。

證明假定an是具有初值的遞歸關系-的任一解。將初值條件代入由r1≠r2知，即兩方程線性無關,解得于是，由上式確定的K1,K2，可求得遞歸關系的一個特解：

例1

求解具有初值條件F0=1,F1=1的遞歸關系Fn=Fn-1+Fn-2。

解特征方程x2-x-1=0的根為：構造通解由初值條件確定K1,K2:從而

例2

求解遞歸關系an-2an-1-2an-2=0，a1=3，a2=8

a0=1。

解特征方程為x2-2x-2=0，特征根為根據初值條件求解K1,K2:故

求a,b,c3個字母組成的n位字符串中，不出現子串“aa”的字符串的個數問題,反映了例2所給遞歸關系的組合學意義。

例3求解n階行列式Dn，其中，主對角元全為2，次對角元全為1，其余都是0。Dn-2Dn-1+Dn-2=0,n≥3

D1=2,D2=3

解相應的特征方程為x2-2x+1=0，二重根為r1=r2=1。通解形式為Dn=K1×1n+nK2×1n=K1+nK2

由初值條件有K1+K2=2

K1+2K2=3解得K1=K2=1。故Dn=1+n

例4求解n階行列式Dn,Dn的主對角元、次對角元均為1，其余都是0。Dn-Dn-1+Dn-2=0

D1=1,D2=0,n≥3解相應的特征方程為x2-x+1=0，一對共軛復根為通解為由初值條件有D1=K1r1+K2r2=1

D2=K1r21+K2r22=0解得最后有例5an-2an-1-2an-2=0(n≥2)

a0=0,a1=1

解特征方程為x2-2x+2=0;一對共軛復根為r1=α+βi，r2=α-βi，α=β=1。解得，θ=π/4，通解為

由初值條件得A=0，求解，得B=1。最后所求特解為an對應的序列為0,1,2,2,0,-4,-8,-8,0,16,32,32,0,…,0。例6求解遞歸關系：an-4an-2=0

a0=0,a1=1解特征方程為x2=4;特征根為r1=2,r2=-2通解形式為故

an=2n-2+(-1)n-12n-2

常系數二階線性齊次遞歸關系的解法，可推廣到高階上去，對此，僅將結果介紹如下。具有初值條件的k階常系數線性齊次遞歸關系：的特征方程為an+c1an-1+c2an-2+…+ckan-k=0

ai=di,i=0,1,2,…,k-1其中，

c0=1，ck≠0。表5.2.1高階線性齊次遞歸關系特征根與通解an中各項的對應關系例7求解遞歸關系an-an-1-9an-2+9an-3=0

a0=0,a1=1,a2=2

解特征方程為x3-x2-9x+9=0;特征根為r1=1,r2=3,r3=-3;通解為an=K11n+K23n+K3(-3)n=K1+K23n+K3(-3)n。故例8求解遞歸關系an-an-2-2an-3-an-4=0

a0=1,a1=1,a2=1,a3=1

解特征方程為x4-x2-2x-1=0,特征根為其中通解為故序列的前幾項是：0,1,1,1,3,4,6,11,17,27,45,72,116,…

n根火柴，甲、乙二人輪流取，每次僅能取1根或2根。若甲先取，求最后由甲取完的方案數有多少種。組合學意義正如本例。5.3常系數線性非齊次遞歸關系的解法

仍以二階遞歸關系為主，考慮遞歸關系an+c1an-1+c2an-2=f(n)其中，關于n的函數f(n)≠0。對初值條件下上述方程的解有如下定理。

定理設an是齊次遞歸關系an+c1an-1+c2an-2=0的通解，而a*n是非齊次遞歸關系an+c1an-1+c2an-2=f(n)的任一特解，則an+a*n即為該方程的通解。

證明令pn為方程an+c1an-1+c2an-2=f(n)的任一解，而a*n為其任一特解。則二式相減，顯見pn-a*n為的解。又已知an是這一齊次方程的通解。即an可用pn-a*n表示，亦即pn可用an+a*n表示。定理得證。為此，欲求解非齊次方程an+c1an-1+c2an-2=f(n)的通解，只需求出an+c1an-1+c2an-2=f(n)的一個特解a*n

。對一般f(n)，尚未找到一個普遍適用的求a*n的方法。但對f(n)較簡單的情形，可有如下解法：（1）f(n)=c1（c為常數）。令A為待定常數，則若1不是特征根，k=0若1是特征方程的k重根

例1求解an-13an-2+12an-3=3。

解特征方程x3-13x+12=0的特征根為1,3,-4，且齊次通解為k1+k23n+k3(-4)n。因1是1重根，故取k=1。特解形式為代入原方程，求得A=-3/10。故非齊次通解為其中K1,K2,K3為任意常數。

例2求解遞歸關系an-2an-1=1。

解齊次遞歸關系的特征方程x2-2x=0的特征根為r1=0,r2=2。1不是特征根，故取a*n=A。遞歸關系的通解為an=K10n+K22n+A。若用初值a0=0,a1=1，則有K2=1，A=-1，即an=2n-1為遞歸關系的特解。（2）

f(n)=cn（c為常數）。令A為待定常數，則若c不是特征方程的根，k=0若c為特征方程的k重根

例3求解an-4an-1+4an-2=2n的通解。

解特征方程x2-4x+4=0的特征根為r1=r2=2。故其特解形式為a*n=An22n，代入遞歸關系可求得A=1/2。故原非齊次遞歸關系的通解為其中，K1,K2為任意常數。

例4求解an+2an-1+an-2=2n。

解特征方程為x2+2x+1=0，特征根為r1=r2=-1，因2不是特征根，故特解形式為將a*n代入an+2an-1+an-2=2n,求得A=4/9。遞歸關系的通解為其中，K1,K2為待定常數。

（3）f(n)=cnPm(n)，其中c為常數，Pm(n)是關于n的m次多項式。其特解形式為c不是特征方程的根，k=0c是特征方程的k重根其中，

Qm(n)是與Pm(n)同次的多項式。例5

求解an+4an-1+an-2=n(n-1)。解c=1,f(n)=n2-n。求得特征根為c=1不是特征根，故特解形式為代入遞歸關系有6An2+6(-2A+B)n+2(4A+3B+3C)=n2-n

比較等式兩邊同次冪系數，可得原非齊次遞歸關系通解為其中，K1,K2為任意常數。

例6求解遞歸關系an-2an-1=n3。

解此例c=1，f(n)=n3。求解特征方程x2-2x=0，得特征根r1=0，r2=2。因c=1不是特征根，故特解為an*=An3+Bn2+Cn+D將其代入an-2an-1=n3，解得A=-1,B=-6,C=-18,D=-26原遞歸關系的通解為an=K22n-n3-6n2-18n-26

例7求和14+24+…+n4。解令an=14+24+…+n4

，則由特征方程r2-r=0知,1是1重特征根，可得非齊次特解為

將其代入an-an-1=n4，比較ni的系數(i=0,1,2,3,4),可求得即非齊次特解為又因相應齊次遞歸關系的通解為由初值a0=0可求得K=0，故非齊次通解為5.4迭代法求解遞歸關系例1求解“Hanoi塔”問題:解例2(錯排問題)

解錯排問題所得結果為非線性遞歸關系。由題初值易得D0=1。整理原遞歸關系有Dn-nDn-1=-(Dn-1-(n-1)Dn-2)從而于是注意到D0=1有最后得例3

求解非線性遞歸關系：解由得例4求解非線性遞歸關系：解從而例5

求解遞歸關系：解例6

求解遞歸關系：解

例7對a,b,c,d4個字母構成的n位字符串，要求不出現“ab”，“ba”子串。求滿足條件的不同n位字符串數目。

解令xn表示以a或b開頭的n位字符串的方案數；yn表示以c或d開頭的n位字符串的方案數，則可得如下遞歸關系:消去含y的項,得解特征方程x2-3x-2=0,得特征根為通解為考慮初值x0=0,x1=2，有解得又因為yn=xn+xn-1

故解得5.5生成函數方法求解遞歸關系定理設具有初值條件的k階常系數線性遞歸關系為其中ck≠0，di是給定常系數，那么，{an}有生成函數其中

是不大于k-1次的多項式。當且僅當{an}關于遞歸關系的特征方程為證明設序列{an}的特征多項式和生成函數分別為G(x)=a0+a1x+a2x2+…+ak-1xk-1+akxk+…+anxn+…由遞歸關系，有將以上等式組兩邊相加，并注意c0=1，有即亦即其中，多項式P(x)的次數不大于k-1，c0=1。易知注意到（k次）特征多項式在復數域上有k個零點，可設從而

例1

已知序列{an}的生成函數為 ，求an。解法1

由定理1用x替代1/x,知特征方程為特征根為故利用整式除法知a0=1/2，a1=3/4解得從而解法2故例2

求如下遞歸關系的生成函數:解特征方程為對

k=2，c0=1，c1=c2=-1，F0=1，F1=1，求得例3求的生成函數。解例4

試求如下遞歸關系中{hn}的生成函數：解設解G2(x)-G(x)+x=0,得注意到，在第二章介紹二項式系數時，已有結論：從而因{hn}是正整數序列，故取最后有或

例5

將一個n+3邊的凸多邊形用不相交的n條對角線分成若干三角形，求不同的分解法。

解令Cn+1表示對n+3邊形的不同分解法的數目。并規定C0=1,C1=1，現考慮n≥2時Cn+1的遞歸關系。固定一點v及其對邊a所成三角形T，則T將凸多邊形分成了兩部分M1,M2，設M1有k+2條邊（k=0,1,2,…,n,而k=0時意味著M1不存在），于是M2有n-k+2條邊。顯見對k+2邊形M1有Ck種分解法，對M2有Cn-k種分解法。

由乘法原理，對某一固定點k，有CkCn-k種分解法。令k遍取0,1,2,…,n，可有如下遞歸關系式：這正是Catalan數列的形式。由生成函數的一般討論即知例6求解遞歸關系：解設生成函數為G(x)=a1x+a2x2+a3x3+a4x4+…則-2xG(x)=-2a1x2-2a2x3-2a3x4+…

-2x2G(x)=-2a1x3-2a2x4+…三式相加并利用遞歸關系，有(1-2x-2x2)G(x)=a1x+(a2-2a1)x2=3x+2x2從而令則比較系數有即有于是由此例7

求解Hanoi塔問題：

解設 ,對等式hn=2hn-1+1，兩邊對應乘以xn，n=2,3,…。并將等式組左右兩邊相加。左端為：h2x2+h3x3+…+hnxn+…=G(x)-x

右端為：解方程得即有從而hn=2n-1

例8

求圖5.5.1所示n級電路圖的等效電阻Rn。

解所謂等效電阻，相當于用一個電阻Rn取代整個電路，使在兩端點n和n′之間與原電路網絡有同樣效果。圖5.5.1等效電阻Rn組成的n級電路圖

Rn可視為Rn-1等效電阻與最后一組電路串并聯構成。由歐姆定律，有因此令R=1（取單位電阻），可有再令Rn=an/bn，則a1=b1=1，從而由此，有方程組(5.5.1a)(5.5.1b)設{an},{bn}的生成函數分別為不難由(5.5.1a)和(5.5.1b)兩式求得：

即解得由于所以又所以從而注意到 ，故對上式右端最后一個分式的分子分母同除以 ，可得

例9對給定存放于單元K(i)中的元素ai(i=1,2,…,n)，要求按照遞增次序進行排序。

解

(1)直接選擇排序法：第一步，從n個數中選出最大者，與K(n)中的數交換位置；第二步，從n-1個數中選出次大者，與K(n-1)中的數交換位置；

……

經n-1步，排序完成。

如下僅用比較次數計算該算法的時間復雜性。設T(n)表示用直接選擇排序算法對n個元素排序所需的比較次數。則因第一次選最大元的比較次數為n-1，剩余的比較次數為T(n-1)。故由加法原理有如下遞推關系：解得可見T(n)與n2同階。(2)分治合并算法：