![《组合数学》教案3章(递推关系)_第1页](http://file4.renrendoc.com/view5/M00/26/2E/wKhkGGZGdJyABDXLAAGIlo6QNSo820.jpg)
![《组合数学》教案3章(递推关系)_第2页](http://file4.renrendoc.com/view5/M00/26/2E/wKhkGGZGdJyABDXLAAGIlo6QNSo8202.jpg)
![《组合数学》教案3章(递推关系)_第3页](http://file4.renrendoc.com/view5/M00/26/2E/wKhkGGZGdJyABDXLAAGIlo6QNSo8203.jpg)
![《组合数学》教案3章(递推关系)_第4页](http://file4.renrendoc.com/view5/M00/26/2E/wKhkGGZGdJyABDXLAAGIlo6QNSo8204.jpg)
![《组合数学》教案3章(递推关系)_第5页](http://file4.renrendoc.com/view5/M00/26/2E/wKhkGGZGdJyABDXLAAGIlo6QNSo8205.jpg)
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
第三章递推关系
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
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 绝缘电阻和吸收比试验
- 2024年印度二氟一氯乙烷行业状况及未来发展趋势报告
- 铁路劳动安全附有答案
- 高二上学期数学北师大版(2019)选择性必修第一册第一章空间向量与立体几何同步单元必刷卷(基础卷)(全解全析)(含答案)
- 红色之旅少先队活动方案
- Ni‒Al双金属催化吡啶与1,3-二烯的对映选择性C2‒H烷基化
- 二元一次方程测试卷
- 高三数学一轮复习题型与战法精准训练(新高考专用)3.3.1导数的恒能成立问题、零点问题、不等式证明问题(题型战法)(原卷版+解析)
- 公司军训心得体会15篇
- 书香校园演讲稿
- 新高速公路护坡劳务合同2024年
- 藤编工艺在非物质文化遗产保护考核试卷
- NB-T+31010-2019陆上风电场工程概算定额
- 借款合同的会议记录
- 2024年动物屠宰检疫及疫病检验员等技能及相关规定知识试题库(附含答案)
- 2024年高考英语新课标II卷及答案
- 网络视频监控系统SmartPSS使用说明书
- 工艺纪律检查表
- 2024年教师师德师风专题培训
- 道德与法治教研组活动计划
- 高校实训室管理员面试
评论
0/150
提交评论