《組合數(shù)學》教案3章(遞推關(guān)系)

第三章遞推關(guān)系

1.遞推關(guān)系及其分類

2.成立應用問題的遞推關(guān)系的方法

3.求解線性常系數(shù)遞推關(guān)系的特色根方法

4.求解遞推關(guān)系的其他方法

5.三個典型數(shù)列及其應用

§3.1基本觀點

（一）遞推關(guān)系

【定義】（隱式）對數(shù)列ai0和隨意自然數(shù)n，

i

一個關(guān)系到an和某些個ain的方程式，稱為遞推關(guān)系，

i

記作

Fa,a,,a0

01n

例a2a2a2a2n20

nn1n20

a3a2a2a10

nn1n21

【定義3.1.1】（顯式）對數(shù)列ai0，把a與其之

in

前若干項聯(lián)系起來的等式對所有n≥k均成立（k為某個給定

的自然數(shù)），稱該等式為ai的遞推關(guān)系，記為

,a,,a

aFa1n2nk（）＇

nn

例a3a2a2a1

nn1n21

word

（二）分類

（1）按常量部分：

①齊次遞推關(guān)系：指常量＝0，如

F

FF；

nn1n2

②非齊次遞推關(guān)系，即常量≠0，如h2h1。

nn1

（2）按a的運算關(guān)系：

i

①線性關(guān)系，F(xiàn)是對于的線性函數(shù)，如（1）中的

aiFn

與h均是這樣；

n

②非線性關(guān)系，F(xiàn)是a的非線性函數(shù)，如

i

hhh。

hhhhn11

n1n12n2

（3）按a的系數(shù)：

i

①常系數(shù)遞推關(guān)系，如（1）中的與；

Fnhn

②變系數(shù)遞推關(guān)系，如pnp，p以前的系數(shù)

nn1n1

是跟著n而變的。

（4）按數(shù)列的多少：

①一元遞推關(guān)系，此中的方程只波及一個數(shù)列，如

（）和（）＇均為一元的；

②多元遞推關(guān)系，方程中波及多個數(shù)列，如

a7ab

nn1n1

b7ba

nn1n1

（5）顯式與隱式：

y

xn

yhy1

n1nn12

yn

1

word

（三）定解

【定】（定解）稱含有初始條件的推關(guān)系定解，其一般形式

Fa,a,,a0,

01n

（）

ad,ad,,ad

0011k1k1

解推關(guān)系，指依據(jù)式（）或（）求a的與a、a、?、a沒關(guān)

n01n－1

的分析表達式或數(shù)列{a}的母函數(shù)。

n

（四）例

【例】（Hanoi塔）n個按從小到大的序一次套在柱A上。

定每次只好從一根柱子上搬一個到另一根柱子上，且要求在

搬程中不允大放在小上，并且只有A、B、C三根柱子可供使

用。用an表示將n個從柱A移到柱C上所需搬的最少次數(shù)，

成立數(shù)列{a}的推關(guān)系。

n

ABC

（解）特例：a＝1，a＝3，于任何n≥3。

12

一般情況：：

第一步，將套在柱A的上部的n－1個按要求移到柱B上，

共搬了a次；

n1

word

第二步，將柱A上的最大一個盤移到柱C上，只需挪動一

次；

第三步，再從柱B將n－1個盤按要求移到柱C上，也要

用a次。

n1

a2a1,

nn1

由加法法例：（）

a1

1

n

求解an＝21

【例】（Lancaster戰(zhàn)斗方程）兩軍打仗，每支軍隊在每日

戰(zhàn)斗結(jié)束時都盤點人數(shù)，用a0和b0分別表示在戰(zhàn)斗打響前第

一支和第二支軍隊的人數(shù)，用an和bn分別表示第一支和第二

支軍隊在第n天戰(zhàn)斗結(jié)束時的人數(shù)，那么，a－a就表示

n－1n

第一支軍隊在第n天戰(zhàn)斗中損失的人數(shù)，相同，b－b表

n－1n

示第二支軍隊在第n天戰(zhàn)斗中損失的人數(shù)。

假定：一支軍隊所減少的人數(shù)與另一支軍隊在每日戰(zhàn)斗開

始前的人數(shù)成比率，則

a

aAb

n1nn1

b

n1bBa

nn1

常量A、B——胸懷每支軍隊的武器系數(shù)

a

an1Ab

nn1（）

b

bBa

nn1n1

——含有兩個未知量的一階線性遞歸關(guān)系組。

n

nk

2

rk，求{a}所知足的遞推關(guān)

【例】設an

n

k

k0

系。

word

（解）x——下整數(shù)函數(shù)。即不大于x的最大整數(shù)。

n

nn-1n-2n

22

arr＋?＋2r

n為偶數(shù)：n＝

012n

2

n1

nn-1n-2n-1

n為奇數(shù)：＝rr22

＋?＋r2

an012n-1

2

分兩種狀況：當n為偶數(shù)時，令n＝2m，則

2

1＝n＝m－1

n

22

2mk

m

k

an＝r

k

k0

2m2mkm

m1m

＝＋kr

r＋

0km

k1

2m2mk1

m1

＝＋rk

0k

k1

m12mk1m

＋rk＋rm

k1k1m

前兩項乞降：

2m

2m

2mk1m1k1

m1

rkrk＝

0

kk

k1k0

n1

2n1k

rka

n1

k0k

后兩項乞降：

word

2m

m2j2m1

rrj＋r

rm1

jm1

j0

n2

2m2j2n2j

m1

jrj＝ra

＝rr＝rn2

j

j0j0j

a＝a＋ra

nn1n2

當n奇數(shù)也成立。求

初：a＝a＝1。

01

a＝a＋ra＝1＋r，a＝a＋ra＝1＋2r，

210321

a＝a＋ra＝(1＋2r)＋r(1＋r)＝1＋3r＋r2

432

2

a＝a＋ra＝(1＋3r＋r)＋r(1＋2r)＝1＋4r＋

543

3r2

【例】0出偶數(shù)次的n位八制數(shù)共有an個，0出奇數(shù)次的

數(shù)共有b個。求a和b足的推關(guān)系。

nnn

0出偶數(shù)次的n位八制數(shù)分兩種狀況：

（1）最高位是0，其他n－1位含有奇數(shù)個0，八制數(shù)共

有b個。

n1

（2）最高位不是0，其他n－1位含有偶數(shù)個0，八制數(shù)共

有7個。

an1

所以有an＝7an1＋bn1。同理可得bn＝an1＋7bn1，

所以a、b足

nn

,

an7anbn1

1

bn7bnan,

11

a17,b11

例n＝2

0出偶數(shù)次的數(shù)00，11，12，13，14，15，?，77，

共50個

0出奇數(shù)次的數(shù)01，10，02，20，03，30，?，70，

word

共14個

yyx,

【例】用退后的Euler公式求常微分方程y

y01

的數(shù)解。

（解）函數(shù)y＝y(tǒng)(x)在點x的真y(x)，近似

nn

yn，求數(shù)解即利用數(shù)方法求y(x)在xn的近似yn（n＝

1,2,??）。

思想：以直代曲。

向前的Euler方法：yyhfx,y，此中h

n1nnn

＝xn1xn稱步。

向后的Euler方法：退后的Euler公式是指常微分方程

yfx,y，當已知函數(shù)y在的，可通解代數(shù)

xn

方程yn1ynhfxn1,yn1求得函數(shù)y在xn1的

數(shù)解yn1，此中h＝xn1－xn是自量x的步（n＝

0,1,2,?）。

word

x

2，代入Euler公式

已知原方程為yfx,yy

y

可得函數(shù)y的數(shù)值解為

yyx

yn1

n1nhn12

y

n1

y1

0

（五）本章研究內(nèi)容

1.建模；

2.求解。

§3.2常系數(shù)線性遞推關(guān)系

常系數(shù)的線性遞推關(guān)系：

acacaca0,c0（）

n1n12n2knkk

或

anc1an1c2an2ckankfn,ck0（）分別稱為k階齊次

遞推關(guān)系和k階非齊次遞推關(guān)系。此中f(n)

word

稱為自由項。

明顯，式（）起碼有一個平庸解an0n0,1,2,，而人們更關(guān)

懷的是它的非零解。

結(jié)論：對于常系數(shù)線性遞推關(guān)系的定解問題，其解必是獨

一的。

求解方法：首推特色根法。

思想：根源于解常系數(shù)線性微分方程，因為二者在結(jié)構(gòu)上

很近似，所以其解的結(jié)構(gòu)和求解的方法也近似。

§3.2.1解的性質(zhì)

【性質(zhì)1】設數(shù)列和是（）的解，則

12

bn

bn

rb1rb2也是（）之解。此中r1、r2為隨意常

1n2n

數(shù)。

（證）b1、b2知足方程（），即

nn

b1cb1cb1cb10,①

n1n12n2knk

b2cb2cb2cb20,②

n1n12n2knk

令r×①＋r×②得：

12

kkk

rcb1rcb2crb1rb20

1ini2inii1ni2ni

i0i0i0

（規(guī)定c＝1，下同）。

0

1s

【推行】設bn,b，，bn均為（）之解，

n2

s

則brbi也是（）的解。此中r,r,,r為隨意

nin12s

i1

常數(shù)。

word

121

【性質(zhì)2】設dn和dn是（）的解，則bndn

d2是（）的解。

n

【性質(zhì)3】若b是（）的解，d是（）的解，

nn

則db是（）的解。

nn

一般情況：設d是（）的解，b1,b2，，bs

nnnn

s

分別是（）的解，則dbi是（）的解。

nn

i1

k

1ca

【性質(zhì)4】設dn是遞推關(guān)系f1n的解，dn

ini2

i0

k

是遞推關(guān)系cafn的解，則dd1d是遞

ini2nnn2

i0

k

f

推關(guān)系canfn的解。

ini12

i0

§3.2.2解的結(jié)構(gòu)

（一）觀點

acacaca0,c0（）

n1n12n2knkk

【定義】稱多項式

C(x)＝xkcxk1cxk2cxc

12k1k

為齊次遞推關(guān)系（）的特色多項式，相應的代數(shù)方程

kk1k2

C(x)＝xcxcxcxc＝0

12k1k

稱為（）的特色方程，特色方程的解稱為（）的特

征根。

word

（二）結(jié)論

n

【定理】數(shù)列anq（）的非零解的充足必需條件是q為（）

的特色根。

（證）aqn是（）的解

n

qncqn1cqnk0

1k

qkcqk1c0

1k

q是方程C(x)＝0的根，即q是（）的特色根。

意義：將求解常系數(shù)線性齊次遞推關(guān)系的問題轉(zhuǎn)變成常系

數(shù)代數(shù)方程的求根問題，進而給出了一個適用且比較簡單的解

此類遞推關(guān)系的方法。

（三）通解

【定義】若s是（）的不一樣

12

a,a,,a

解，且（n）的任何解都能夠表為nn

ra1ra2rasa，則稱an為（）的通解。其

1n2nsnn

中r,r,,r為隨意常數(shù)。

12s

i

此地方說的不一樣解是指將每一個解an都視為一個無量

維的解向量，而這些向量之間是線性沒關(guān)的。

說明通解的特色：

①通解a第一是解；

n

②構(gòu)成通解的所有解向量線性沒關(guān)；

③任何一個詳細的解都被包含在通解a中。

n

§3.2.3特色根法

思路：經(jīng)過解式（）的特色方程，求得其特色根，再利用

特色根結(jié)構(gòu)（）的通解。

word

（一）特色根根情況

q,q,,q是（）的互不相同的特色根，（）的通解

12k

aAqnAqnAqn（）

n1122kk

此中A,A,,A隨意常數(shù)（待定）。

12k

n

（）（1）an是（）的解：由定理3.2.1知qi是方程（）的解，再

由性1知a也是（）的解。

n

（2）向量qn,qn,,qn性沒關(guān)：

12k

（）（）的所有解都能夠表（）的形式：b

n

3

是（）的一個解，且足初始條件bd，i＝0,1,2,?,

ii

k

k－1。令bAqn，代入初始條件，得對于的性方

niiAi

i1

程

Aq0Aq0Aq0b

1122kk0

AqAqAqb

1122kk1（）

Aqk1Aqk1Aqk1b

1122kkk1

系數(shù)隊列式范德蒙隊列式：

111

qqq

12k

Dq2q2q2qq0

12kji

1ijk

qk1qk1qk1

12k

所以式（）有獨一解。即b必定能夠表示（）的形式。

n

因為b的隨意性，故知成立。

n

word

【例】求遞推關(guān)系a4aa6a的通解。

nn1n2n3

（解）特色方程為x34x2x60，解之得特色根

q1＝－1，q＝2，q＝3

23

∴通解為aA1nB2nC3n

n

此中，A、B、C為隨意常數(shù)。

假如定解問題，設初值為：a5，a13，a35，帶

012

入通解得

ABC5

A2B3C13

A4B9C35

解得A＝0，B＝2，C＝3，故

nn23

a2233n1n1

n

若初值為a＝－，＝，則

0

12

417

a31n2n

n

求A、B、C的方程組為

ABC4

A2B3C1

A4B9C7

規(guī)律：

（二）重根情況

【例】求遞推關(guān)系a4a4a0的通解。

nn1n2

word

（解）特色方程x24x40

特色根qq2（二重根）

12

仿單根情況an＝A2nA2n＝AA2n＝A2n

1212

一個待定常數(shù)。

問題：知足兩個初始條件ad,ad不太可能。

0011

本質(zhì)：兩個解向量a12n和a22n是線性有關(guān)的。

nn

任務：找兩個線性沒關(guān)的解向量a1和a2。

nn

另一解：令a2n2n，也是解，且與a12n線性沒關(guān)。

nn

a4a4a

nn1n2

＝n－－1＋4(n－2)＝0

nn2

24(n1)2n2

a1a210

00

＝2

a1a22

112

通解：aA2nAn2n（需證明）

n12

一般情況：設q為k重根，則通解為

aAAnAnk1qn

n12k

更一般的情形：有t個根，q為k重根

ii

t

i1,2,,t;kk。通解

i

i1

tki

aAnj1qn

niji

i1j1

A

k1n

AnAn1q

11121k1

1

AnAnk21qn

A21222k2

A2

k

Ant1n

t1t2Anq

tkt

t

【例】求an7a19a25a16a4an5＝0

n1n2n3n4

的通解。

（解）特色方程x57x419x325x216x4＝0

特色根：x＝1（三重），x＝2（二重）

word

通解a＝(A＋An＋An2)1n＋(A＋An)2n

n1112132122

＝(A＋An＋An2)＋(A＋An)2n

1112132122

（三）復根情況

設特色方程有一對共軛（單）復根：qei，qei，

則通解中含

nee

AqnBq＝AninBnin

＝Acosnisinn＋Bncosnisinn

n

＝ABncosn＋iABnsinn

＝Acosn＋Ansinn

1n2

通解：an＝AncosnAnsinn

12

長處：防止了復數(shù)運算。特別是當數(shù)列{an}是實數(shù)時，

n

AqnBq的虛部為零。

一般情況：q是m重復根，也是m重復根，通解中有

q

AAnAnm1cosn＋

n12m

BBnBnm1sinn

12m

小結(jié)：

特色根通解中對應的項

實q為單根Aqn

根m重根AAnAnm1qn

12m

一對單復根

qei,AcosnAsinn

n12

復qei

根一對m重復根

nm1

qei,AAnAncosn

12m

qeiBBnBnm1sinn

12m

word

a2a2a0

nn1n2

【例】求定解。

a0,a1

01

（解）特色方程：q2－2q＋2＝0

28

特色根：＝4＝±i

q1

2

（方法I）按復根形式：2，

4

nn

n

通解：an＝2AcosBsin

44

A0

代初：

2A2B21

22

n

解：A＝0，B＝1

sin

定解：

an2

n

4

0,當n4m

＝1m22m,當n4m1，m＝0,1,?

m,

121當n4m2,4m3

2m

數(shù)列：0，1，2，2，0，-4，-8，-8，0，16，-32，-32，?

（方法II）按根形式：

通解：aA1inB1in

n

i

A

代入初：AB0，即2

1iA1iB1i

B

2

ni1

定解：ai1ii

nn

22

化復數(shù)表示形式數(shù)形式

nn

ai2ncosisin

n

244

word

nn

i2cosisin

nn

244

＝2isin2

i＝sinn

nn

44

【例】求定解

a4ia54ia45ia44ia4ia0

nn1n2n3n4n5

a5,a6,a10,a24,a50

01234

（解）特色方程：

q54iq454iq345iq244iq4i＝0

特色根：q＝2，2，i，i，－i

通解：a＝ABn2nCDninEin

n

ACE5

2ABCDiE(i)6

代初：4A2BC2DE10

8A3BC3DiEi24

16A4BC4DE50

解：A＝3，B＝0，C＝1，D＝0，E＝1

nn

定解：an＝32ii

n

32n21n/2,當n4m,4m2

＝，

32n,當n4m1,4m3

n＝0,1,?

（四）代數(shù)方程求根

方程：axnaxn1axa＝0，在復數(shù)域上

nn110

必有n個根x,x,,x（k重根按k個算）。

12n

word

xxx1na

12n0

a

n

（1）韋達定理a

n1

x1x2xn

a

n

（）推論：例中，方程460如有整數(shù)

32

2xxx

根，則此根必整除-6，即此根必為±1，±2，±3，±

6之一。

（3）方程的降階：由韋達定理知-1是解，方程必可分解為

x1x2axb＝0

§3.2.4非齊次方程

（一）結(jié)構(gòu)

困難性：與微分方程近似。

可解情況：f(n)的幾種特別情況。

acacaca0（）

n1n12n2knk

acacacafn（）

n1n12n2knk

a*a

【定理】設n是（）的一個特解，n是（）的通解，則

（）的通解為

aa*a

nnn

（證）（1）a是解；（2）a是通解。（近似齊次情況）

nn

意義：問題歸納為求非齊次遞推關(guān)系的特解。

（二）待定系數(shù)法

目的：求特解a*

n

困難：無一般通用方法

特例：當自由項f(n)比較簡單時，采納待定系數(shù)法

（一）f(n)＝b（b為常數(shù)）

word

a*Anm

n

m表示1是m重特色根。若1不是特色根（即m＝0），則a*

n

＝A。

（二）fnbn（b為常數(shù)）

a*＝Anmbn

n

m表示b是m重特色根。若b不是特色根，則*n。

anAb

（三）fnbnPn，此中Pn為對于n的r次多項式，

rr

b為常數(shù)。

a*＝nmbnQn

nr

Qrn是與Prn同次的多項式，m是b為特色根的重數(shù)。當

b不是特色根時，a*bnQn。

nr

（三）例

【例】求非齊次方程a－13a＋12a＝3的通解。

nn－2n－3

（解）剖析：方程右側(cè)為常數(shù)3

特色方程：q3－13q＋12＝0

特色根：q＝1，3，-4，m＝1

特解：a*＝An（A稱為待定系數(shù)）

n

代入遞推關(guān)系：An－13A(n－2)＋12A(n－3)＝3

整理得－10A＝3

3

解之A＝，故為

10

通解：a＝B＋Bn＋B－。此中、B、B為任

n123n－3123

3(4)nB

10

意常數(shù)。

【例】求遞推關(guān)系a－4a＋4a＝2n的通解。

nn－1n－2

（解）剖析：方程右側(cè)為2n

word

特色根：q＝2（二重根），

特解：a*＝An22n

n

2n12222n

代入原式：An22n－4An12＋4Ann2＝

睜開：An22n－2A(n2－2n＋1)22n＋A(n2－4n＋4)22n＝2n

整理：2A2n＝2n

1

待定系數(shù)：A＝

2

1

通解：＝2n＋2n＋22n＝n2

anB1B2nnB1Bn12n。

2

22

此中B、B為隨意常數(shù)。

12

【例】求a＋4a＋a＝n(n－1)的通解。

nn－1n－2

（解）剖析：方程右側(cè)為多項式：f(n)＝n2－n（b＝1）

特色根：q＝－2±3（b＝1不是特色根）

特解：a*＝An2＋Bn＋C

n

代入原方程：

An2BnC＋4An-12Bn-1C

＋An-2Bn-2C＝－

2

n(n1)

整理：6An2－6(2A－B)n＋2(4A－3B＋3C)＝n2－n

比較兩邊同類項的系數(shù)：

6A1

62AB1

24A3B3C0

11

解得A＝，B＝，C＝

1

6618

通解：a＝n＋13n3n1。此中、B為

nn2

B1q1B2q218B12

隨意常數(shù)。

word

（四）化非齊次方程為齊次方程

n

【例】求sk。

n

k0

（解）（1）sn知足的遞推關(guān)

snsn,

系n1

s00

注：不可以用迭代法求

解。

（2）化為齊次遞推關(guān)系

改寫遞推關(guān)系

s

snn1n①

近似得

s

snn2n1②

1

①－②得

sn2sn1sn1③

2

同理

s2ss

n1n2n31④

s

sn3sn13sn2n30,

③－④得

s00,s11,s23

規(guī)律：左側(cè)升階，右側(cè)降階。

（3）求解

特色根：q＝1是三重根。

sABnCn21n＝ABnCn2

n

代初值s00,s11,s23：

A0

ABC1

A2B3C3

word

1

∴A＝0，B＝C＝

2

∴s1n1n＝nn1

n2

222

用遞推關(guān)系證了然乞降公式

nn1

12n

2

（五）一般乞降公式

n

（1）問題：求srkr

n

k0

（2）化為齊次遞推關(guān)系求解

第一，當r＝1時，由（四）知

sABnCn2

n

當r＝2時，可得

s

2

snn1n①

s

2

snn2n1②

①－②得1

s

s2s2n1③

nn1n2

s

2ss2n11④

n1nn

③－④得23

s

s3s3s1⑤

nn1n2n3

ss

n13s3sn41⑥

n2n3

⑤－⑥就得對于s的齊次定解問題

n

sn4sn16sn24sn3sn40,s00,s11,

s5,s14

23

特色根仍舊是q＝1（四重），所以

2

sABnCnDn3

n

再利用初值條件得

nn12n1

s

n6

word

（3）迅速求常數(shù)A、B、C、D等

當r＝1時，令

s＝ABnCnn1

n

A0

代入初始條件后得AB1

A2B2C3

11

解得A＝0，B＝1－A＝1，C＝－－＝

(3A2B)

22

1nn1

∴snnn1

n

22

長處：不需要解線性代數(shù)方程組，即可逐漸遞推地解出系

數(shù)A、B、C等。

另法：令

sABnCnn1

n2！

A0

代入初值條件AB1

A2BC3

解得A＝0，B＝1－A＝1，C＝3－A－2B＝1

長處：在利用初值確立A、B、C時更為方便。因為方程

中分別對于A、B、C的系數(shù)恰巧是1，不做除法。

當r＝2時，可令

nn1nn1n2

snABnCD

2！3！

代入初值s0,s1,s5,s14得方程組

0123

word

A0

AB1