組合數(shù)學(xué)課件4常系數(shù)遞歸關(guān)系

《圖論與組合優(yōu)化》第五講常系數(shù)遞歸關(guān)系1第四講:常系數(shù)遞歸關(guān)系2I.常系數(shù)齊次遞歸關(guān)系特征值為不同的實(shí)數(shù)特征值均為實(shí)數(shù)但是有重根特征值有復(fù)根*II.常系數(shù)非齊次遞歸關(guān)系*I.常系數(shù)齊次線性遞歸關(guān)系3其中a1

,a2

,,ar是實(shí)常數(shù),

f(n)非零.常系數(shù)線性遞歸關(guān)系有齊次和非齊次兩種.設(shè)Hn是一個(gè)遞歸數(shù)列.常系數(shù)齊次遞歸關(guān)系:Hn

-a1Hn-1

-a2Hn-2

--ar

Hn-r

=

0

(4.1)常系數(shù)非齊次遞歸關(guān)系:Hn

-a1Hn-1

-a2

Hn-2

--ar

Hn-r

=

f

(n)假定ar≠0,則遞歸關(guān)系(4.1)稱為是r階的.如果序列中r個(gè)相鄰的H值Hk-r,Hk-r+1,…,Hk-1對(duì)某一k已知,則可用(4.1)算出Hk的值,于是Hk+1,Hk+2,…的值也可遞歸的算出.所以(4.1)的解唯一的由r個(gè)相鄰的H值(邊界條件)所決定.因此,(4.1)的解的一般形式包含有r個(gè)待定常數(shù),這些常數(shù)可由序列中相鄰的r個(gè)H值來(lái)決定.一般給定初值:H0,H1,…,Hr-1.4對(duì)于(4.1)中的r階齊次遞歸關(guān)系:Hn

-

a1

Hn-1

-

a2

Hn-2

-

-

ar

Hn-r

=

0我們定義如下的一元r

次方程:xr

-a

xr-1

-a

xr-2

--a x

-a

=

0(4.2)1

2

r-1

r稱(4.2)為(4.1)的特征方程.特征方程的根叫原遞歸關(guān)系的特征根(值).5定理設(shè)q1,q2是二次齊次遞推方程

Hn+2+a1Hn+1+a2Hn=0的兩個(gè)特征根，則Hn是遞推方程的解的充要條件是Hn可表成如下形式：6當(dāng)q1≠q2時(shí)，2

2Hn=b1q1n+b

q

n;

(1)當(dāng)q1=q2=q時(shí)，Hn=(b1+b2n)qn

(2)其中b1,b2為常數(shù)。證明：充分性.當(dāng)q1≠q2時(shí),將(1)代人遞推方程的左邊，因q1,q2是特征根，有721

221

11

1

12

22

1

12

21

1

12

21

1q

+

a

q

+

a

)=

0+

b

q

(q

+

a

q

+

a

)=

b

q

(+

b

q

))+

a

(b

q+

b

q+

a

(b

qH

+

a

Hn

22

2

2n

2nnn+1+

a

H

=

b

qn+2

+

b

qn+22

n1

n+1n+1n+2即

Hn=b1q1n+b2q2n

是遞推方程的解。當(dāng)q1=q2=q時(shí),將(2)代人遞推方程的左邊，因q是重根，2q+a1=0812

212122

121

121(2q

+

a

)=

0q

+

b

q=

(b

+

b

n)q

(

+

a

q

+

a

)+

a

(b

+

b

n)q+

a

(b

+

b

(n

+1))qqb

+

b

(n+

a

H

=

(

+

2))n+1n

2nn+1n+2n+1

2

nHn+2

+

a1

H即

Hn=(b1+b2n)qn

是遞推方程的解。必要性設(shè)Hn是二次齊次遞推方程Hn+2+a1Hn+1+a2Hn=0的解，因?yàn)閝1,q2是兩個(gè)特征根，由韋達(dá)定理，q1+q2=-a1,q1q2=a2,代人遞推方程，得Hn+2-(q1+q2)Hn+1+

q1q2Hn=0,即得9Hn+2-q1Hn+1=q2(Hn+1-q1Hn)Hn+2-q2Hn+1=q1(Hn+1-q2Hn)(3)(4)當(dāng)q1≠q2時(shí)，令Fn=Hn-q1Hn-1，Gn=Hn-q2Hn-1則(3),

(4)式化為Fn+2=q2Fn+1，Gn+2=q1Gn+11所以

Fn+1=q2nF1，Gn+1=q

nG1從而有

Hn+1-q1Hn=q2nF1Hn+1-q2Hn=q1nG1兩式相減，得21Hnq

-

qqn

G

-

qn

F=

1

1

2

1,G1q1

-

q2-

F1,

c2

=q1

-

q2記

c1

=nH

=

c

qn

+

c

qn1

1

2

21011當(dāng)q1=q2=q時(shí)，令Fn=Hn-qHn-1，則(3),

(4)式化為Fn+2=qFn+1，所以

Fk=qk-1F1，從而有Hk=qHk-1+qk-1F1上式兩邊乘于qn-k，再自k=1至k=n取和，得1n

nkk

-1+

nq

n-1

F

qn-k

H

=

qn-k

+1

Hk

=1

k

=1等式兩邊展開(kāi)，得H

=

qn

H

+

nq

n-1

Fn

0

1因?yàn)閍2≠0，故q≠0,

記c1=H0,c2=F1/q,則有H

=

(c

+

c

n)qnn

1

2對(duì)于(4.1)中的r階齊次遞歸關(guān)系:Hn

-

a1

Hn-1

-

a2

Hn-2

-

-

ar

Hn-r

=

0我們定義如下的一元r

次方程:xr

-a

xr-1

-a

xr-2

--a x

-a

=

0(4.2)1

2

r-1

r稱(4.2)為(4.1)的特征方程.特征方程的根叫原遞歸關(guān)系的特征根(值).下面我們根據(jù)特征根的情況來(lái)給出相應(yīng)的解法.121.

有r個(gè)不同的實(shí)特征根13定理4.1設(shè)q1,q2,…,qr是遞歸關(guān)系(4.1)的r個(gè)互不相同的實(shí)特征根,則其一般解為:2

2

r

rn

n

nHn

=

c1q1

+c

q

++c

q

(4.3)證(1)先證(4.3)一定是原來(lái)的遞歸關(guān)系的解.在(4.3)式當(dāng)中,令n

取n-1,n-2,…,n-r,得到r個(gè)等式:142

22

21

1r

rn-1

n-1

n-1

1

1n-2n-1r

rn-2

n-2

n-2n-rn-r

n-rn-r

1

1

2

2

r

r

HH

H=

c

q=

c

q

+

c

q

+

+

c

q+

c

q

+

+

c

q=

c

q

+

c

q

+

+

c

q2

1

21

1

12

2

2n-1r

1

rn-1

n-11

n-1n-2r

2

rn-2

n-2

2

n-2

1

2

1n-r2

r

2

r

r

rn-r n-r+

c

a

q

a

H

=

c

a

q+

c

a

qa

H

=

c

a

q+

c

a

qr n-r

=

c1arq1a

H++

c

a

q++

c

a

q++

c

a

q把這r個(gè)等式相加并整理,右邊正好是(4.3)的右邊,即得到15n

n

n2

2

r

rHn

=

c1q1

+

c

q

+

+

c

q=

a1

Hn-1

+

a2

Hn-2

+

+

ar

Hn-r這說(shuō)明(4.3)中定義的數(shù)列滿足定理4.1中的遞歸關(guān)系(4.1).從而證明了對(duì)任意參數(shù)c1,c2,…,cr而言(4.3)都是定理中遞歸關(guān)系的一個(gè)解.(2)下面證明任何一個(gè)解都可以表示成

(4.3)的形式.對(duì)任意一個(gè)解hn來(lái)說(shuō),它由邊界條件h0=b0,h1=b1,…,hr-1=br-1完全確定.由(1)我們知道(4.3)定義的數(shù)列都滿足定理中的遞歸關(guān)系.我們需要證明由這些邊界條件可以完全決定一般解(4.3)中的參數(shù)c1,c2,…,cr.1617

1

12

2

r

-1r

-1r

-1r

-11

1

2

2

r

r

1c

q

+

c

q+

+

crqr

=

b

c

q

+

c

q

+

+

c

q

=

b我們使用待定系數(shù)法來(lái)證明c1,c2,…,cr存在性.根據(jù)需要可以得到聯(lián)立方程組c1

+

c2

+

+

cr

=

b0這個(gè)方程組的系數(shù)矩陣的行列式在著名的Vandermonde行列式.因?yàn)樗械奶卣髦祋1,q2,…,qr都不相同,所以這個(gè)行列式不為零.于是原方程組關(guān)于c1,c2,…,cr有唯一解.說(shuō)明在這種條件下(4.1)的解是唯一確定的.r

-1181

2

rr

-1r

-1qqqq1

q2

qr

1

1

1例4.1

Fibonacci數(shù)列的遞歸關(guān)系:Fn=

Fn-1+

Fn-2, F0

=F1=1

(4.4)可以利用特征值的方式來(lái)求解這個(gè)遞歸關(guān)系.解該遞歸關(guān)系的特征方程為x2-x-1=0,其特征根為19可設(shè)該數(shù)列的解為:221

2=

1

-

5q

=

1

+

5

,

q2n

1

-

5

2n

1

+

5

+

c2

Fn

=

c1

20

=

12

2

1

+

5

1

-

5

+

c2

c

1由邊界條件得到方程組c1

+

c2

=

1解這個(gè)方程組得到:225

5211

?1

-

51

?1

+

5

,c

=c

=所以,該遞歸數(shù)列的解為.2125251

1

-+1

1

+5

n+15

n+1Fn

=例4.2

求解遞歸關(guān)系Hn

=

2

Hn-1

+

Hn-2

-

2

Hn-3

,H0

=

1,

H1

=

2,

H

2

=

0,(n

=

3,4,).解該遞歸關(guān)系所對(duì)應(yīng)的特征方程:22x

3

-

2

x

2

-

x

+

2

=

0特征根:

x1

=

1,

x2

=

-1,

x3

=

2.設(shè)遞歸關(guān)系:n

n

nHn

=

c11

+

c2

(-1)

+

c3

2由邊界條件確定常數(shù)c1,c2,c3.需要解下列=

1

1

2

31

2

3c

+

c

+

4c

=

0c1

-

c2

+

2c3

=

2線性方程組:

c

+

c

+

c33321=

-

1

.=

-

2

,

cc

=

2,

c3

323nH

=

2

-

2

(-1)n

-

1

2n.解之可得:通解為:例4.3在信道上傳輸僅用3個(gè)字母a,b,c組成并且長(zhǎng)度為n的詞.規(guī)定連續(xù)出現(xiàn)兩個(gè)a的詞不能傳輸.試確定這個(gè)信道允許傳輸?shù)脑~的個(gè)數(shù).解令h(n)為允許傳輸長(zhǎng)度為n的詞總數(shù),n=1,2,….

直接計(jì)算知,h(1)=3,h(2)=8.設(shè)n≥3,第一個(gè)字母是b或c的詞數(shù)均為

h(n-1);第一個(gè)字母是a的詞,第二個(gè)字母必須是b或c,這種詞的數(shù)目為2h(n-2).故有以下遞歸關(guān)系:h(n)

=

2h(n

-

1)

+

2h(n

-

2),

n

=

3,4,且h(1)=3,

h(2)=8.該遞歸關(guān)系的特征方程為x

2

-

2

x

-

2

=

0243

,

q2

=

1

-

3其特征根為：q1

=

1

+故一般解為:n

nh(n)

=

c1

(1

+

3

)

+

c2

(1

-

3

) ,

n

=

3,4,由邊界條件h(1)=3,

h(2)=8

解方程組：2

1c

(1

+

3

)2

+

c

(1

-

c1

(1

+

3

)

+

c2

(1

-

3

)

=

33

)2

=

82

32

321=

-

2

+

3

.c

=

2

+

3

,

c3

)n

+

-

2

+

3

(1

-

3

)n2

3

25h(n)

=

2

+

3

(1

+2

32.

特征根有重根的情況26解特征方程:對(duì)于這種情況,我們只通過(guò)例題說(shuō)明求解方法,最后給出一般結(jié)論,不詳細(xì)推導(dǎo).例4.4

求解遞歸關(guān)系:Hn

=

6Hn-1

-

9Hn-2

,

H0

=

1,

H1

=

2可見(jiàn)3是二重特征根.此時(shí),除了Hn=3n這個(gè)解之外,還有一個(gè)解:Hn=n3n.x2

-

6

x

+

9

=

(

x

-

3)2

=

0一般解可設(shè)為:n

nHn

=

c1

3

+

c2

n3利用邊界條件得到線性方程組并求解:2

13c

+

3c

=

2c1

=

131

2c

=

1,

c

=

-

1

.327n=

3n

-

1

n3n

=

3n

-

n3n-1.解為：H定理4.2

設(shè)q1,q2,…,qt是遞歸關(guān)系28ar

?

0(n

=

r,

r

+

1,)全部不同特根,

qi的重?cái)?shù)為ei(i=1,2,…,t),則該遞歸關(guān)系對(duì)應(yīng)于qi部分的一般解是:H

(n)

=

a1

H

(n

-1)

++

ar

H

(n

-

r

),ninin

nqii

1

i

2

i

eie

-1ei

-1=

(c1

+

c2

n

+

+

ce

n

)qiH

(n)

=

c

q

+

c

nq

+

+

c

n全部通解：H

(n)=H1

(n)+H

2

(n)+

+Ht

(n)僅有兩個(gè)有復(fù)特征根*當(dāng)特征方程有復(fù)數(shù)根時(shí),

因?yàn)閺?fù)數(shù)根總是成對(duì)出現(xiàn)的,而且任意復(fù)數(shù)a+bi都可以寫(xiě)成ceid的形式,故可設(shè)兩個(gè)復(fù)根分別為a1

=

d

+

iw

=

re

=

r

(cosq

+

i

sinq

,iqa2

=

d

-

iw

=

re

=

r

(cosq

-

i

sinq

),-iq.29

=

tan-1

d

w其中

r

==

d

2

+

w

2

,q此時(shí)這兩個(gè)根對(duì)應(yīng)的一般解部分為:30l

an

n1

1

2

2+

l

a=

l

rn

(cosnq

+

i

sinnq)

+

l

rn

(cosnq

-

i

sinnq)1

2=

(l

+

l

)rn

cosnq

+

i(l

-

l

)rn

sinnq1

2

1

2因此這部分解也可以設(shè)為:Arn

cos

nq

+

Brn

sin

nq其中A,B為待定參數(shù),可利用邊界條件得到.例4.5給定邊界條件a1=1,a2=0,求解遞歸關(guān)系:an

=

an-1

-

an-2

.解該遞歸關(guān)系對(duì)應(yīng)的特征方程為:x

2

-

x

+

1

=

0其特征根為:1

331x

=

1

-

i

3

.2

2

2x1

=

2

+

i

2

,所以該遞歸關(guān)系的一般解可設(shè)為:an

=

Ar

cos

nq

+

Br

sin

nqn

n其中.3231232p

=

2=

1,q

=

tan

3

+

2

2

1

2r

=-1na

=

Acos

np

+

B

sin

np

.3

3由邊界條件a1=1,a2=0,便可決定A和B,這只需要解下列方程組:=

032p3+

B

sin

A

cos

A

cos

p

+

B

sin

p

=

1332p31A

=

1,

B

=3333

3na

=

cos

np

+

1

sin

np

.例有n枚相同的棋子，甲、乙兩人輪流取子，每次可取1至2枚，取完為止。求首尾兩次都是甲取子的取法種數(shù)Hn.解：遞推方程為Hn+4

-

Hn+2

-

2Hn+1

-

Hn

=

034規(guī)定

H0

=

0其中

H1

=

H2

=

H3

=

1,

H4

=

3其特征方程為x4

-

x2

-

2x

-1

=

04個(gè)特征根為2352222121b

=

1

(1

-

5

)b

=

1

(1

+

5

),3),

a

=

1

(-1

-

i

3)a

=

1

(-1

+

i所以，通解為nH

=

c

a

n

+

c

a

n

+

b

b

n

+

b

b

n1

1

2

2

1

1

2

2其中c1,c2,b1,b2為待定常數(shù)把初始條件代人通解，得方程組2

231

132

22222

22

2

1

11

121

13

1

1+

bc

a

+

c

a

+

b

b+

b1

b1

+

b2

b2

=

1b

3

=

1c

a

+

c2a

2c

a

+

c

a

+

b

b

+

b

b

=

1c1

+

c2

+

b1

+

b2

=

0解得2361

212

512

512

32

3b1

,

b2

=

-

ba

2

,

b1

=ia

,

c

=

-ic

=II.常系數(shù)線性非齊次遞歸關(guān)系*37線性非齊次遞歸關(guān)系:Hn

-

a1

Hn-1

-

-

ar

Hn-r

=

f

(n)這里,a1,…,ar全部是常數(shù).例如:24Hn

-

3Hn-1

+

2Hn-2

=

n

+

5Hn

=

2Hn-1

+

3Hn

=

Hn-1

-

n

+

3都是常系數(shù)線性非齊次遞歸關(guān)系.常系數(shù)線性非齊次遞歸關(guān)系的求解方法與非齊次線性方程組的求解思路類似.非齊次通解=齊次通解+非齊次特解.齊次通解求法已介紹.問(wèn)題歸結(jié)為如何尋找遞歸關(guān)系的特解.對(duì)于尋找遞歸關(guān)系的特解,還沒(méi)有一般方法.通常根據(jù)f(n)的組成形式,由觀察法來(lái)決定特解.

當(dāng)函數(shù)f(n)比較復(fù)雜時(shí),用觀察法來(lái)決定特解是相當(dāng)困難的.38當(dāng)非齊次項(xiàng)是多項(xiàng)式時(shí),可通過(guò)增加遞歸關(guān)系的階,降低非齊次項(xiàng)的冪次,從而化成齊次遞歸關(guān)系求解.下面通過(guò)一個(gè)例題來(lái)說(shuō)明這種升階法.例

4.5

平面上有n條直線,

任何兩條直線不平行,且任何三條直線不交于一點(diǎn),問(wèn)共有多少個(gè)交點(diǎn)？解令hn為n條直線的交點(diǎn)個(gè)數(shù).第n條直線與前n-1條有n-1個(gè)交點(diǎn),故有遞歸關(guān)系hn=hn-1+n-1,且h1=0,

h2=1,

h3=3.39下面是通過(guò)增階化為齊次的過(guò)程:hn=hn-1+n-1,

(1)hn-1=hn-2+n-2,

(2)(1)式-(2)式整