《组合数学》教案3章(递推关系)

第三章递推关系

1.递推关系及其分类

2.建立应用问题的递推关系的方法

3.求解线性常系数递推关系的特征根方法

4.求解递推关系的其它方法

5.三个典型数列及其应用

§3.1基本概念

（-）递推关系

【定义3.1.1】（隐式）对数列｛。小＞0｝和任意自然数n,

一个关系到和某些个叫。＜〃）的方程式，称为递推关系，

记作

尸（&O，4，…，&〃）=。

例a；-心-----=°

----为「1=0

【定义3.11］（显式）对数列｛%|，20｝,把。〃与其之前

若干项联系起来的等式对所有nek均成立（k为某个给定的

自然数），称该等式为｛七｝的递推关系，记为

例an=3a„_t+2aL2+•••+为+1

(二)分类

(1)按常量部分：

①齐次递推关系：指常量=0,如尸〃=尸,1+Fn_2；

②非齐次递推关系，即常量W0,如儿一24_1=1。

(2)按的运算关系：

①线性关系，F是关于%的线性函数，如(1)中的死

与儿均是如此；

②非线性关系，F是6的非线性函数，如

K=—+—2+…+*1klo

(3)按的系数：

①常系数递推关系，如(1)中的耳，与

②变系数递推关系，如P"="”_[，p,i之前的系数

是随着n而变的。

(4)按数列的多少：

①二①遢推差系，其中的方程只涉及一个数列，如

(3.1.1)和(3.1.1)'均为一元的；

②曳元递推关系，方程中涉及多个数列，如

「a”=7a—+b—

、么=7dl+i

(5)显式与隐式：

jr

y,i=y+h

t+nL%+"

(三)定解问题

【定义3.1.2](定解问题)称含有初始条件的递推关系为定

解问题，其一般形式为

，内，…，4〃）=°，

(3.1.2)

d。,4=出，…,

解递推关系，指根据式（3.1.1）或（3.1.2）求an的与a。、

西、…、a。」无关的解析表达式或数列｛%｝的母函数。

（四）例

【例3.1.1】（Hanoi塔问题）〃个圆盘按从小到大的顺序一

次套在柱A上。规定每次只能从一根柱子上搬动一个圆盘到

另一根柱子上，且要求在搬动过程中不允许大盘放在小盘上，

而且只有A、B、。三根柱子可供使用。用魅表示将〃个盘从

柱A移到柱C上所需搬动圆盘的最少次数，试建立数列｛%｝

的递推关系。

（解）特例：供=1,。2=3,对于任何〃23。

一般情形:：

第一步，将套在柱A的上部的n-1个盘按要求移到柱B

上，共搬动了％t次；

第二步，将柱A上的最大一个盘移到柱。上，只要搬动一

次；

第三步，再从柱8将〃一1个盘按要求移到柱C上，也要

用Q“_i次。

ci..=2a]+1,

由加法法则：\""nT（3.13）

%=1

求解«„=2n-l

【例3.1.2］（Lancaster战斗方程）两军打仗，每支军队在

每天战斗结束时都清点人数，用“0和瓦分别表示在战斗打响

前第一支和第二支军队的人数，用“和勿分别表示第一支和

第二支军队在第n天战斗结束时的人数，那么，%_］一魅就表

示第一支军队在第n天战斗中损失的人数，同样，九一1一九表

示第二支军队在第n天战斗中损失的人数。

假设：一支军队所减少的人数与另一支军队在每天战斗开

始前的人数成比例，则

au-l-an=Abn-l

也=跖-1

常量A、B——度量每支军队的武器系数

a„=a”［一Ab„,

\n"T"T（3.1.4）

4=bn-i-Ba,I

——含有两个未知量的一阶线性递归关系组。

【例3.1.31设%=£rk,求同｝所满足的递推关

SIy

系。

（解）Ld——下整数函数。即不大于x的最大整数。

(

n-1、1-2、n

22I

n为偶数：an=+r+r+-+r

41><2>n

<2>

n+1、

'n-1、、-2、n-1

为奇数：册=2F2

n4-r+r+-+1

OJ<1><2,n-1

~T>

分两种情况：当n为偶数时，令n=2m,则

(2m2m-R-P卜

+E

<0k=l\k7

'm\

+E-+m

A=l1k一\,jn7

前两项求和:

(2

+?.rk=>

后两项求和:

m-1'

2rJ+r

j=o\j)m-1,

〃一2

an=an-l+ran-2

当n为奇数时也成立。

求初值：a0=ai=lo则

。2=。1+m0=l+r,。3=。2+叫=l+2r,

。4=。3+r42=(l+2r)+r(l+r)=l+3r+r2

22

as=a4+r43=(l+3r+r)+r(l+2r)=l+4r+3r

【例3.1.4］设0出现偶数次的n位八进制数共有％个，0

出现奇数次的数共有。“个。求册和，满足的递推关系。

对0出现偶数次的n位八进制数分两种情况讨论：

(1)最高位是0,则其余n—l位应该含有奇数个0,这类

八进制数共有〃1个。

(2)最高位不是0,则其余n—l位还应该含有偶数个0,

这类八进制数共有7%个。

因此有%=7%_i+bn_xo同理可得2=%_1+7b「i，所

以明、勿满足

a”=7"”一1+b，

«bn=73_1+a”_i，

ci=7,bi=1

例n=2

0出现偶数次的数00,lb12,13,14,15,77,

共50个

0出现奇数次的数01,10,02,20,03,30,70,

共14个

，_入

【例3.1.5］用后退的Euler公式求常微分方程)=丁一丁

.X0)=1

的数值解。

(解)函数y=y(x)在点Xn处的真值记为y(xn),近似值记

为yn，求数值解即利用数值方法求y(x)在处A的近似值yn(n

=1,2,.......)o

思想：以直代曲。

向前的Euler方法：y“+i=%+hf(xn,%),其中h

=xn+i-%”称为步长。

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

/=/(x,j),当已知函数y在％处的值时,可通过解代数

方程yn+i=y,i+好(x〃+i，y”+i)求得函数y在Xn+l处的

数值解匕,+1，其中力=乙+1一/是自变量X的步长(〃=

0,1,2,-)o

已知原方程为y'=/(x,j)=J-2-,代入Euler公式

y

可得函数y的数值解为

,L—

V

%+1=%+为4+1-23

<L4+i」

Jo=1

(五)本章研究内容

1.建模；

2.求解。

§3.2常系数线性递推关系

常系数的线性递推关系：

%+9%+。2。”一2+••=0,(q¥o)(3.2.1)

或

an+C1《I+c2aA2+../(h)，(q，o)(3.2.2)

分别称为k阶齐次递推关系和k阶非齐次递推关系。其中f(n)

称为自由项。

显然，式（3.2.1）至少有一个平凡解°“=0（〃=0,1,2广）,

而人们更关心的是它的非零解。

磐：对于常系数线性递推关系的定解问题，其解必是唯

一的。

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

思想：来源于解常系数线性微分方程，因为两者在结构上

很类似，所以其解的结构和求解的方法也类似。

§3.2.1解的性质

【性质11设数列｛瓦T）｝和｛乐2）｝是（3.2.1）的解，则

｛。以）+*｝也是（3.2.1）之解。其中小r2为任意常

数。

（证）｛氏I）卜｛瓦考满足方程（3.2.1）,即

州）++。2d2+…化=。，①

娟+。阳+C阅2+••q-=。，②

令口*①+r2X②得：

+々2。陷=2，（4剂+々型）=o

1=0z=0<=0

（规定5=1,下同）。

【推广】设｛即｝,｛区2）｝,…，｛次S）｝均为（3.2.1）之解,

则［“=名也是（321）的解。其中大小…为任意

、i=l,

常数。

【性质2】设｛d州和｛^)｝是(3.2.2)的解，则

｛a=d1)一《2)｝是(3.2.1)的解。

【性质3】若仇｝是(3.2.1)的解，｛d“｝是(3.2.2)的解,

则｛凡±2｝是(3.2.2)的解。

一般情形:设｛dj是(322)的解，｛即｝，｛丛叫…，/)｝

分别是(3.2.1)的解，则也+是(3.2.2)的解。

【性质4】设｛则是递推关系之c,4i"(〃)的解，刚

1=0

是递推关系=%(")的解，贝河风=40+$2)｝是递

i=0

推关系X=71㈤+『2㈤的解。

1=0

§3.2.2解的结构

(一)概念

an+C\an-\+C2an-2+'Ckan-k~°，(&*0)(3.2.1)

【定义3.2.1】称多项式

kkxk2

C(x)=x+clx~+c2x~+--+ck_lx+ck

为齐次递推关系(3.2.1)的特征多项式，相应的代数方程

kk—1

C(x)=X+C]X+C2xH-----1-Ck_xX+ck=0

称为(3.2.1)的特征方程，特征方程的解称为(3.2.1)的特征

根。

（二）结论

【定理3.2.1］数列4=/（3.2.1）的非零解的充分必要条

件是q为（3.2.1）的特征根。

（证）是（3.2.1）的解

0/+6产+­+6«尸=0

k

<=>q+---+ck=0

<=>q是方程C（x）=0的根，即q是（3.2.1）的特征根。

里：将求解常系数线性齐次递推关系的问题转化为常系

数代数方程的求根问题,从而给出了一个实用且比较简单的解

此类递推关系的方法。

（三）通解

【定义3.2.2］若｛即｝，…乂心）｝是（3.2.1）的不同

解，且（3.2.1）的任何解都可以表为

广弁）+々。£）+3+/;小）=4"，贝称。”为（3.2.1）的通解。其

中小々，…北为任意常数。

此处所说的不同解是指将每一个解｛4"｝都视为一个无穷

维的解向量，而这些向量之间是线性无关的。

说明通解的特征：

①通解明首先是解；

②组成通解的所有解向量线性无关；

③任何一个具体的解都被包容在通解明中。

§3.2.3特征根法

思路：通过解式（3.2.1）的特征方程，求得其特征根，再

利用特征根构造（3.2.1）的通解。

(-)特征根为单根情形

设名,生,…，%是(3.2.1)的互不相同的特征根，则

(3.2.1)的通解为

a„=4球+4久---卜4土文?(3.2.3)

其中A，4,…,4为任意常数(待定)。

(证)(1)。〃是(3.2.1)的解：由定理3.2.1知4：是方

程(3.2.1)的解，再由性质1知%也是(3.2.1)的解。

(2)向量｛端｝,｛久｝,…,｛或｝线性无关：

(3)(3.2.1)的所有解都可以表为(3.2.3)的形式：设勿

是(3.2.1)的一个解，且满足初始条件=4,i=0,l,2,-,k

-lo令a=24片,代入初始条件，得关于A的线性方程

1=1

组

A%+^2q24+,Akqk=b0

<R24)

4--1+一#】+...+41-1=%

系数行列式为范德蒙行列式：

11…1

%…Qk

。=q；q；Qk=n(公-/卜。

武…武

所以式(3.2.4)有唯一解。即与一定可以表示为(3.2.3)的形

式。

由于2的任意性，故知结论成立。

【例3.2.1】求递推关系all-4an_l+an_2=-6a„_3的通解。

（解）特征方程为――4，+%+6=0,解之得特征根

%=-1,q2=2,q3=3

・•・通解为a=A（-1）W+B2"+C3K

其中，A、B、C为任意常数。

若是定解问题，设初值为：。。=5,«,=13,g=35,带

入通解得

A+B+C=5

-A+2B+3C=13

A+4B+9C=35

解得A=0,B=2,C=3,故

%=2・2"+3・3"=2"+】+3"+i

若初值为“o=4,=—1,%=7,贝!j

%=3（-1）"+2"

求A、B、C的方程组为

A+B+C=4

-A+2B+3C=-1

A+43+9C=7

规律：

（二）重根情形

【例3.2.2】求递推关系-他I+4aA2=。的通解。

(解)特征方程％2-4%+4=0

特征根%=%=2(二重根)

仿单根情形%=A2"+42"=(4+&)2"=A2"

一个待定常数。

问题：满足两个初始条件4=4),%=4不太可能。

实质：两个解向量=2"和a?)=2"是线性相关的。

任务：找两个线性无关的解向量心)和

另一解：令af)=zi2",也是解，且与a2=2"线性无关。

^,-^-1+^-2

=n2"-4(n-l)2,,_,+4(n—2)2"“=o

10

大)“旷22

通解：。“=42"+劣〃2"(需证明)

一般情形：设q为k重根，则通解为

=(A+A2/I+…+4〃J)q"

更一般的情形：有t个根，%为左重根

(t\

i=1,2,…由£kj=ko通解

ki=lJ

i=lj=l

=(Ai+Ann+…+A&"J)q；

n-n

+(41+^22I^2k2)^2

+…+(4+Atin+…+)q；

【例3.2.3】求a,,-7a“T+l%“_2-25a“_3+l&i—-T=0

的通解。

(解)x5-7x4+19x3-25x2+16x-4=0

特征根：x=l(三重)，x=2(二重)

通解=(Au+Ai2〃+A13〃2)l"+(421+422〃)2"

=(A11+A12〃+A13〃2)+(A21+A22〃)2"

(三)复根情形

设特征方程有一对共粗(单)复根：q=peie,q=pe-ie,

则通解中含

Aq"+Bq"=ApneinG+Bpne-inG

—A/y[cos(鹿6)+isin(7ze)]+3/y[cos(〃e)_isin(〃创

=(A+B)p"cos(〃6)+i(A—B)p"sir(n0)

=A0"cos(〃e)+A2p"siv(n0)

nn

通解：«„=Axpcos(w6)+A2psin(〃6)+…

优点：避免了复数运算。尤其是当数列｛%｝是实数时，

Aq"+Bq"的虚部为零。

一般情形：q是m重复根，》也是m重复根，通解中有

P[(A++…+jcos(ne)+

ml

(禺+2"+…+Bltln)sin(/i<9)]

小结:

特征根通解中对应的项

实q为单根Aq"

根

m重根(A+4"+,,,+A/T

一对单复根

q=/，“[Acos(〃e)+4sin(〃e)]

复q=pe~ie

根一对m重复根,,,-1

p"｛Ax+AJHH---FAZ;IH)COS(/2^)

+(B,+B2n++B/i)sin(〃e)

q=pe~ie

•i—5a„~2a”i+2a„,=0

【例3.2.4】求定解「"T"-2o

〃0=0,Q]=1

（解）特征方程：q2—2q+2=0

必/p+s2±V4-8.

特征根：q=--------------=l±l

2

（方法I）按复根形式：p=V2,0=-

4

通解：an=（V2）fAcos—+Bsin^

V44J

4=0

代初值：1痣0

V2A—+B—=1

II22J

解：A=0,B=1

定解：an=（V2）1si弓

0,当〃=4/%

=«（-1），?，22"',当〃=4/ra+l,m=0,1,…

（-1）W,22m+1,当〃=4m+2,4m+3

数列：0,1,2,2,0,-4,-8,-8,0,16,-32,-32,…

（方法H）按单根形式：

通解：=A（1+i）"+B（1-i）"

A=~-

代入初值：[（/+:”、，即2

I2

定解：%-：（1+i）"+：（1-i）"

化复数表示形式为实数形式

1171

+,—IV石2Icos------r•sin•——

2V7V44）

=­i（42^isin^-=（72^'sin^-

【例3.2.51求定解

&-（4+泣t+（5+4必t一（4+5M-3+（4+4%…-4也_5=0

«

即=5,%=6,a2=10,a3=24,a4=50

（解）特征方程：

q5―（4+iV+（5+4iV_（4+5必2+（4+4M-4i=0

特征根：q=2,2,i,i,-i

通解：氏=（A+Bn）2n+（C+Dn）i"+E（-i）"

A+C+E=5

2（A+B）+（C+D）i+E（-i）=6

代初值：4（A+2B）-（C+2D）-E=10

8（A+3B）-（C+3D）i+Ei=24

16（A+43）+（C+4D）+E=50

解：A=3,B=0,C=LD=0,E=1

定解：a”=3•2"+i"+（—i）"

3・2"+2（—1）”;当〃=4机,4机+2

<

3・2”,当〃=4机+1,4机+3

〃=0,l,…

（四）代数方程求根

方程：+…=0,在复数域上

必有n个根与，X2,…，芍低重根按k个算）。

/”/=(一1)》

(1)韦达定理《”

/+芍+…+x“=一一—

I

(2)推论：例3.2.1中，方程，一4，+%+6=0若有整数

根，则此根必整除-6,即此根必为±1,±2,±3,+6

之一。

(3)方程的降阶：由韦达定理知-1是解，方程必可分解为

(x+iX^2+ax+))=0

§3.2.4非齐次方程

(-)结构

困难性：与微分方程类似。

可解情形：f(n)的几种特殊情形。

%+G/i++…Q%=°(3.2.1)

%+一%+c2al+…Q%=/(")(3.2.2)

【定理3.2.2］设。:是(3.2.2)的一个特解，乙是(3.2.1)

的通解，则(3.2.2)的通解为

*一

(证)(1)%是解；(2)。”是通解。(类似齐次情形)

意义：问题归结为求非齐次递推关系的特解。

(-)待定系数法

目的：求特解。：

困难：无一般通用方法

特例：当自由项f(n)比较简单时，采用待定系数法

(一)f(n)=b(b为常数)

n

an=An'

m表示1是m重特征根。若1不是特征根(即m=0),则a：

=Ao

(二)f(n)=b'1(b为常数)

nn

an=Aiib

m表示b是m重特征根。若b不是特征根，则

(H)f(n)=b"Pr(n),其中为关于n的r次多项式,

b为常数。

mn

an=nbQr(n)

0(〃)是与《(")同次的多项式，m是b为特征根的重数。当

b不是特征根时，an=b"Qr(«)。

(三)例

【例3.2.6】求非齐次方程an-13an-2+12an_3=3的通解。

(解)分析：方程右边为常数3

特征方程：q3-13q+12=0

特征根：q=L3,-4,m=l

特解：a：=An(A称为待定系数)

代入递推关系：An—13A(n—2)+12A(n_3)=3

整理得一10A=3

解之A=-4,故为

nn

通解：an=B1+B23+B3(-4)-^no其中B】、B2>B3为任

意常数。

n

【例3.2.7】求递推关系an-4an-1+4an-2=2的通解。

(解)分析：方程右边为2"

特征根：q=2(二重根)，

特解：a；=An22n

代入原式:An22"-4A("-1)22nl+4A(n-2)22n-2=2n

展开：An22z,-2A(n2-2n+l)22H+A(n2-4n+4)22n=2"

整理：2A2"=2"

待定系数：A=1

2

H2n12

通解：an=Bi2"+B2n2+-n2=|Bt+B2n+-n2"

2v2o

其中Bi、B2为任意常数。

【例3.2.8】求an+4an-i+an-2=n(n—1)的通解。

(解)分析：方程右边为多项式：f(n)=n2—n(b=l)

特征根：q=-2±V3(b=l不是特征根)

2

特解：an=An+Bn+C

代入原方程：

(An2+Bn+C)+4(A(n-l)2+B(n-1)+C)

+(A(n-2)2+B(n-2)+C)=n(n—1)

整理：6An2-6(2A-B)n+2(4A-3B+3C)=n2-n

比较两边同类项的系数：

6A=1

<-6(2A-B)=-1

2(4A-3B+3C)=0

解得A=-,B=-,C=-—

6618

通解：=3闯：+层4'+—(3n2+3n—1)«其中Bi、B2为

18

任意常数。

（四）化非齐次方程为齐次方程

【例3.2.9］求s“=力R。

4=0

（解）（I）S“满足的递推关系=

bo=°

注：不能用迭代法求解。

（2）化为齐次递推关系

改写递推关系

类似得

S,T-S〃—2=〃T②

①一②得

Sn~2S〃_1+s„-2=1③

同理

%T-2S〃_2+S〃-3=1④

…s„—3s”i+3s”—s„a=0,

③一④得《""Tn-27"3

、s（）=0,“=1,§2=3

规律：左边升阶，右边降阶。

（3）求解

特征根：q=l是三重根。

s“=（A+Bn+Cn2）tl）"=A+Bn+Cn2

代初值（s（）=0,§i=l,§2=3）：

A=0

•A+B+C=l

A+2B+3C=3

.1,1_n（n+1）

•・s„=—n+—n

'222

用递推关系证明了求和公式

YC+1）

l+2+---+n=--------

2

（五）一般求和公式

（1）问题：求也）二E-

A=0

（2）化为齐次递推关系求解

首先，当r=l时,由（四）知

2

sn=4+Bn+Cn

当r=2时,可得

=/①

S,I-Sa-2=（〃-1）2②

①一②得

%-2%_1+%_2=2〃-峥

-2sl+%-3=-1）-1@

③一④得

S

n-33〃T+3%_2一%-3=1⑤

S

n-1~3S”-2+3S“_3-S”_4=1⑥

⑤一⑥就得关于S”的齐次定解问题

S“_4%_]+6s_-4s_+s_=0,

Vn2n3n4

ss

o=。,=1,2=5,s3=14

特征根仍然是q=l（四重），所以

23

slt=A+Bn+Cn+Dn

再利用初值条件得

n（n+1X2/1+1）

6

(3)快速求常数A、B、C、D等

当后1匹令

s==4+Bn+Cn(n—1)

4=0

代入初始条件后得，A+B=l

A+2B+2C=3

解得A=0,B=l-A=l,C=-(3-A-2B)=-

22

•*-Sn=〃+；〃(〃-1)="

优点：不需要解线性代数方程组，即可逐步递推地解出系

数A、B、C等。

另法：令

力=4+加+。巫生

n2!

A=0

代入初值条件•A+B=l

A+2B+C=3

解得4=0,B=1~A=1,C=3-A-2B=1

优点：在利用初值确定A、B、C时更加方便。因为方程

中分别关于A、B、C的系数恰好是1,不做除法。

当r=2时,可令

一+即

"2!3!

代入初值(s()=0,$1=1,s2=5,S3=14)得方程组

A=0

A+B=l

A+2B+C=5

A+3B+3C+D=14

A=0,B=l,C=3,D=2

n[n—1)n{n—1)(鹿—2)_n(n+1)(2〃+1)

s=w+3I乙=

n266

对于较大的r,求部分和s'?时，利用非齐次递推关系

s”=S-+nr求解还是要比将其化为齐次递推关系方便得

多。

（4）一般情形

若通解％为r阶多项式匕（〃），对定解问题（3.1.2）,可令

岸（"）=4+++…+A］；

使得用初值条件求解常数4非常简单。

§3.2.5一般递推关系化简

对于某些非线性或变系数的递推关系，可以将其化为线性

关系来求解。

*2

【例3.2.10］解定解问题%一卅%=°，

旬=L

（解）线性变系数一阶齐次关系。改写

an=小％i

两边取对数：In%=+Inn+n2

令…」得［………2,

Po=0.

再令力(〃)=加〃，人(〃)=/。化为两个递推关系

2

b,「"-1=In〃，和[2一"_]=n,

4=。♦1%=0.

用迭代法解=E"',得即=Inn!,

?o=0・

用待定系数法解["一%得从2)/(〃+1)(2〃+1).

4=0.6

从而得

,..w(//+1Y2H+1)

b„=lnn!+—----△-------L

“6

加加|"("+1'2"+1)"("+1)(20+1)

6h6

an=e=e'"'e

.,Fn(n+1Y2H+1)

.•a“=nl-exp----------------

【例3.2.11】解定解问题卜%+&%=2“，心1

WQ一乙ID.

(解)线性变系数一阶非齐次关系。

b"+b-=2",

令得

a=n%%=0.

n+1

通解为2="(-1)"+2

3

2

由初始条件为=0知6=-—

3

〃+1

・•・2==(一1)"+2=|k-(-i)1]

3

・%=2[2"—(一1)"],n>l

••13n

a[}=273.

即〃]=2,4=1,4=2,&=§，

2

a-na_=nl,n>1

【例3.2.12］解定解问题<nn}

aQ=2.°

（解）线性变系数一阶非齐次递推关系。

难点：/(«)=«!

4味t„>!

观察：n\(n-1)!

4=2

令2=等化为匕-%=1，n>l

n\也=2

特解：b；=n,通解：b“=Bl"+n

an的通解：an=（n+2）nl.

另法：对于2，可以用迭代法或直接观察出a="+2,

再用归纳法证明之即可。

【例3.2.13】设n21时，20,解定解问题

-2片一1=1,n>l

5o

产0=2

（解）常系数非线性二阶递推关系。

b,「2bAi=1,心1

令b”=a：,变为：，

4=4

解之得bn=5•2"-1,从而an=•2"-1。

§3.3解递推关系的其它方法

§3.3.1迭代法与归纳法

适应情况:

1.迭代法：对某些一阶的递推关系，使用迭代法求解可

能更快。

2.归纳法：观察n比较小时””的表达式的规律，总结或

猜出。“的一般表达式，然后用归纳法证明。

_a=2a,..+2Z,,(n>1)

[例3.3.1]\n—')

%=3

(解)变换2=*+i

2n2

逐步迭代：

aaa

—n=--n--\r.4-i1=--n---2-,+2=•••=—^0+,n=n+,5q

2"22"~22

・,.%=2"("+3),(n>1)

当n=0时，上式仍成立(即满足所给的初值)，故解为

an=2"(n+3),(n>0)

另法：先做变量代换2=2(n=l,2,•••),得

2

也(心1)

力0=3

迭代求解：bn=w+3,(w>0)

然后反代回去得%=2"bn=2"1+3),(it>1)

+(-1)\(w>l)

【例3.3.2］解递推关系

a。=3

+（-球

（解）因"=—4("N1)

nl(n—1)!nl

（-ir,（-I）M

迭代得，=a—+

n\5—2）!（w-1）!nl

=3+Zn3=2+

Jk=lNk・'士—=0%k・'

所以%=加2+（〃N1）

当n=0时，上式仍成立，故定解问题的解为

（M>0）

&=4%，（八22）

【例3.3.3】解递推关系《

ao=2,G[=1

（解）由题设

a2k+l

A+1）

所以“24+1=2",a2k=2-（A：>1

当k=0时，上面两个式子仍成立。故

2"\当〃为奇数时

2"+,,当〃为偶数时

或%=2“)”，(心0)

【例33.4］用归纳法解递推关系卜"=%*",(〃之1)

«()=0

(解)计算较小n时的，并观察得

即=0=02

6=1=12=(1+0)2

32

«2=r+2=9=(0+1+2)

%=1+23+33=36=(0+1+2+3)2

由此可猜想

劣=(0+1+2+...+心

再用归纳法证之：显然n=0,1,2,3时结论为真。

假设n=k时结论为真，即以=，:；"成立。

考虑n=k+l时

%+1=取+(1+1)3

=/(1+4)2+仅+1)3=/+皿+2。

结论成立。故对一切非负整数n,有.=\"+")，

4

§3.3.2母函数方法

思路：对较复杂的递推关系，利用母函数求解。

方法：

8

•设欲求解的数列｛an｝的母函数为G(X)=2°“X"；

71=0

•利用递推关系本身求函数G(x)满足的方程(代数方程

或微分方程等)；

•解方程求出G(x)；

n

•将G(x)展开成x的塞级数。则x的系数便是an的解

析表达式(即递推关系的解)。

【例3.3.5］解递推关系

n

an—5an-1+6an-2=2,n>2

(解)(利用无穷求和)：

00

令A(x)=Ea"x",原方程两边同乘x"得

/2=0

n

(%一+6an_2)x=2"x"

nz，

即-5。〃_1工"+6an_2x=(2x)

对n从2到8求和得

00>\8

5(册X"-5a“_3+6*x")=t(2x)〃

n=2n=2

0000800

fa”*"一5口"_/"=£(2X)”

〃=2〃=2〃=2〃=2

力X—5x皂X+6/象"x"=W(2x)"

n—2H=1〃=0/i=2

—2

(A(x)—a0atx)—5x(A(x)—a0)+6xA(x)=--———(l+2x)

l-2x

解之得

o+(Q[_54)xI4x2

A(x)=

1—5x+6x^(1-5x+6/11-2x)

A(x)=——--+—--+------记

l-3xl-2x7(l-2x)2

将A(x)展开

000000

Hn

A(X)=CJ2(3X)+c22(2x)-2E(H+1)(2X)”

/i=0〃=0〃=0

nwn+1w

=£[c13+c22-(W+l)2]x

〃=0

00

〃=0

比较等式两端xn的系数

,,/,,l+1

«„=c13+e22-(n+l)2

式中ci、C2为任意常数，由初值a。和a1确定。

例如，设a()=La1=—2,则q、c2满足下列方程组

c+c—2=l

<l2

3。1+2C2—8=—2

解得5=0,C2=3.

因此满足上述初值条件的递推关系的解为

n+1

an=3X2"-(n+l)2=(1-2n)2"

【例3.3.6】求定解问题=+""一2.

1招=尸2=1

(解)(思路：拆项)。

反推求Fo=F2—F1=O