组合数学课件4常系数递归关系

《图论与组合优化》第五讲常系数递归关系1第四讲:常系数递归关系2I.常系数齐次递归关系特征值为不同的实数特征值均为实数但是有重根特征值有复根*II.常系数非齐次递归关系*I.常系数齐次线性递归关系3其中a1

,a2

,,ar是实常数,

f(n)非零.常系数线性递归关系有齐次和非齐次两种.设Hn是一个递归数列.常系数齐次递归关系:Hn

-a1Hn-1

-a2Hn-2

--ar

Hn-r

=

0

(4.1)常系数非齐次递归关系:Hn

-a1Hn-1

-a2

Hn-2

--ar

Hn-r

=

f

(n)假定ar≠0,则递归关系(4.1)称为是r阶的.如果序列中r个相邻的H值Hk-r,Hk-r+1,…,Hk-1对某一k已知,则可用(4.1)算出Hk的值,于是Hk+1,Hk+2,…的值也可递归的算出.所以(4.1)的解唯一的由r个相邻的H值(边界条件)所决定.因此,(4.1)的解的一般形式包含有r个待定常数,这些常数可由序列中相邻的r个H值来决定.一般给定初值:H0,H1,…,Hr-1.4对于(4.1)中的r阶齐次递归关系: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)的特征方程.特征方程的根叫原递归关系的特征根(值).5定理设q1,q2是二次齐次递推方程

Hn+2+a1Hn+1+a2Hn=0的两个特征根，则Hn是递推方程的解的充要条件是Hn可表成如下形式：6当q1≠q2时，2

2Hn=b1q1n+b

q

n;

(1)当q1=q2=q时，Hn=(b1+b2n)qn

(2)其中b1,b2为常数。证明：充分性.当q1≠q2时,将(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

是递推方程的解。当q1=q2=q时,将(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

是递推方程的解。必要性设Hn是二次齐次递推方程Hn+2+a1Hn+1+a2Hn=0的解，因为q1,q2是两个特征根，由韦达定理，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)当q1≠q2时，令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当q1=q2=q时，令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等式两边展开，得H

=

qn

H

+

nq

n-1

Fn

0

1因为a2≠0，故q≠0,

记c1=H0,c2=F1/q,则有H

=

(c

+

c

n)qnn

1

2对于(4.1)中的r阶齐次递归关系: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)的特征方程.特征方程的根叫原递归关系的特征根(值).下面我们根据特征根的情况来给出相应的解法.121.

有r个不同的实特征根13定理4.1设q1,q2,…,qr是递归关系(4.1)的r个互不相同的实特征根,则其一般解为:2

2

r

rn

n

nHn

=

c1q1

+c

q

++c

q

(4.3)证(1)先证(4.3)一定是原来的递归关系的解.在(4.3)式当中,令n

取n-1,n-2,…,n-r,得到r个等式: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个等式相加并整理,右边正好是(4.3)的右边,即得到15n

n

n2

2

r

rHn

=

c1q1

+

c

q

+

+

c

q=

a1

Hn-1

+

a2

Hn-2

+

+

ar

Hn-r这说明(4.3)中定义的数列满足定理4.1中的递归关系(4.1).从而证明了对任意参数c1,c2,…,cr而言(4.3)都是定理中递归关系的一个解.(2)下面证明任何一个解都可以表示成

(4.3)的形式.对任意一个解hn来说,它由边界条件h0=b0,h1=b1,…,hr-1=br-1完全确定.由(1)我们知道(4.3)定义的数列都满足定理中的递归关系.我们需要证明由这些边界条件可以完全决定一般解(4.3)中的参数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我们使用待定系数法来证明c1,c2,…,cr存在性.根据需要可以得到联立方程组c1

+

c2

+

+

cr

=

b0这个方程组的系数矩阵的行列式在著名的Vandermonde行列式.因为所有的特征值q1,q2,…,qr都不相同,所以这个行列式不为零.于是原方程组关于c1,c2,…,cr有唯一解.说明在这种条件下(4.1)的解是唯一确定的.r

-1181

2

rr

-1r

-1qqqq1

q2

qr

1

1

1例4.1

Fibonacci数列的递归关系:Fn=

Fn-1+

Fn-2, F0

=F1=1

(4.4)可以利用特征值的方式来求解这个递归关系.解该递归关系的特征方程为x2-x-1=0,其特征根为19可设该数列的解为: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解这个方程组得到:225

5211

•1

-

51

•1

+

5

,c

=c

=所以,该递归数列的解为.2125251

1

-+1

1

+5

n+15

n+1Fn

=例4.2

求解递归关系Hn

=

2

Hn-1

+

Hn-2

-

2

Hn-3

,H0

=

1,

H1

=

2,

H

2

=

0,(n

=

3,4,).解该递归关系所对应的特征方程:22x

3

-

2

x

2

-

x

+

2

=

0特征根:

x1

=

1,

x2

=

-1,

x3

=

2.设递归关系:n

n

nHn

=

c11

+

c2

(-1)

+

c3

2由边界条件确定常数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个字母a,b,c组成并且长度为n的词.规定连续出现两个a的词不能传输.试确定这个信道允许传输的词的个数.解令h(n)为允许传输长度为n的词总数,n=1,2,….

直接计算知,h(1)=3,h(2)=8.设n≥3,第一个字母是b或c的词数均为

h(n-1);第一个字母是a的词,第二个字母必须是b或c,这种词的数目为2h(n-2).故有以下递归关系:h(n)

=

2h(n

-

1)

+

2h(n

-

2),

n

=

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

h(2)=8.该递归关系的特征方程为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解特征方程:对于这种情况,我们只通过例题说明求解方法,最后给出一般结论,不详细推导.例4.4

求解递归关系:Hn

=

6Hn-1

-

9Hn-2

,

H0

=

1,

H1

=

2可见3是二重特征根.此时,除了Hn=3n这个解之外,还有一个解:Hn=n3n.x2

-

6

x

+

9

=

(

x

-

3)2

=

0一般解可设为: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

设q1,q2,…,qt是递归关系28ar

„

0(n

=

r,

r

+

1,)全部不同特根,

qi的重数为ei(i=1,2,…,t),则该递归关系对应于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)仅有两个有复特征根*当特征方程有复数根时,

因为复数根总是成对出现的,而且任意复数a+bi都可以写成ceid的形式,故可设两个复根分别为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此时这两个根对应的一般解部分为: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因此这部分解也可以设为:Arn

cos

nq

+

Brn

sin

nq其中A,B为待定参数,可利用边界条件得到.例4.5给定边界条件a1=1,a2=0,求解递归关系:an

=

an-1

-

an-2

.解该递归关系对应的特征方程为:x

2

-

x

+

1

=

0其特征根为:1

331x

=

1

-

i

3

.2

2

2x1

=

2

+

i

2

,所以该递归关系的一般解可设为: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枚，取完为止。求首尾两次都是甲取子的取法种数Hn.解：递推方程为Hn+4

-

Hn+2

-

2Hn+1

-

Hn

=

034规定

H0

=

0其中

H1

=

H2

=

H3

=

1,

H4

=

3其特征方程为x4

-

x2

-

2x

-1

=

04个特征根为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为待定常数把初始条件代人通解，得方程组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.常系数线性非齐次递归关系*37线性非齐次递归关系:Hn

-

a1

Hn-1

-

-

ar

Hn-r

=

f

(n)这里,a1,…,ar全部是常数.例如:24Hn

-

3Hn-1

+

2Hn-2

=

n

+

5Hn

=

2Hn-1

+

3Hn

=

Hn-1

-

n

+

3都是常系数线性非齐次递归关系.常系数线性非齐次递归关系的求解方法与非齐次线性方程组的求解思路类似.非齐次通解=齐次通解+非齐次特解.齐次通解求法已介绍.问题归结为如何寻找递归关系的特解.对于寻找递归关系的特解,还没有一般方法.通常根据f(n)的组成形式,由观察法来决定特解.

当函数f(n)比较复杂时,用观察法来决定特解是相当困难的.38当非齐次项是多项式时,可通过增加递归关系的阶,降低非齐次项的幂次,从而化成齐次递归关系求解.下面通过一个例题来说明这种升阶法.例

4.5

平面上有n条直线,

任何两条直线不平行,且任何三条直线不交于一点,问共有多少个交点？解令hn为n条直线的交点个数.第n条直线与前n-1条有n-1个交点,故有递归关系hn=hn-1+n-1,且h1=0,

h2=1,

h3=3.39下面是通过增阶化为齐次的过程:hn=hn-1+n-1,

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

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