组合数学 3.3常系数线性非齐次递推关系

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,3.3常系数线性非其次递推关系,3.3.1 非其次递推关系,3.3.2 举例,1,3.3.1 非其次递推关系,常系数线性非其次递推关系,a,n,c,1,a,n-1,c,2,a,n-2,c,k,a,n-k,F(n),(,3.3.1,),其中c,1,c,2,c,k,是实数常数，c,k,0；,F(n),是只依赖于n且不恒为0的函数。,相伴的齐次递推关系,a,n,c,1,a,n-1,c,2,a,n-2,c,k,a,n-k,(,3.3.2,),2,3.3.1 非其次递推关系,定理3.3.1,若a,n,x(n)为递推关系(3.3.1)相伴的齐次递推关系(,3.3.2,)的,通解,， a,n,y(n)为递推关系(,3.3.1,)的一个,特解,，则a,n,x(n) y(n)为递推关系(,3.3.1,)的,通解,。,3,3.3.1 非其次递推关系,定理3.3.2,设常系数线性非齐次递推关,a,n,c,1,a,n-1,c,2,a,n-2,c,k,a,n-k,F(n),其中c,1,c,2,c,k,是实数常数，c,k,0；,且,F(n),(b,t,n,t,b,t-1,n,t-1,b,1,n b,0,),S,n,其中b,1,b,2,b,t,和S是实数常数。,当,S,是相伴的线性齐次递推关系的特征方程的,m,(m,0,)重根时，存在一个下述形式的特解：,a,n,n,m,(p,t,n,t,p,t-1,n,t-1,p,1,np,0,),S,n,其中p,1,p,2,p,t,为待定系数。,4,3.3.2 举例,例3.3.1,解递归,解,(1),相伴齐次递推关系a,n,a,n-1,(,),(,)的特征方程x,10,(,)的特征根 x1,(,)的通解a,n,a,1,n,a(a为任意常数),5,3.3.2 举例,(2),由于,F(n),nn,1,n,且s,1,是(,)的,1,重,根，所以得()的一个特解形如,a,n,n,1,(p,1,np,0,),1,n,(p,1,p,0,为待定系数),代入a,1,1，a,2,3得,6,3.3.2 举例,故得()的一个特解,a,n,n,1,( n ),1,n, n,2,n,(3),()的通解,a,n,a n,2,n (a为任意常数),代入a,1,1得a0,(4),求得递归的解a,n, n,2,n,7,3.3.2 举例,例3.3.2,解Hanoi问题的递归,，,即,解,(1),相伴齐次递推关系a,n,2a,n-1,(,),(,)的特征方程x,20,(,)的特征根 x2,(,)的通解a,n,a,2,n,(a为任意常数),8,3.3.2 举例,(2),由于,F(n),11,1,n,且s,1,是(,)的,0,重,根，所以得()的一个特解形如,a,n,n,0,p,1,n,p(p为待定系数),代入()得p,1,故得()的一个特解a,n,1,9,3.3.2 举例,(3),()的通解,a,n,a2,n,1(a为任意常数),代入a,1,1得a1,(4),求得递归的解a,n,2,n,1,10,3.3.2 举例,定理3.3.3,若a,n,x(n)和a,n,y(n)分别是递推关系,a,n,c,1,a,n-1,c,2,a,n-2,c,k,a,n-k,F,1,(n),a,n,c,1,a,n-1,c,2,a,n-2,c,k,a,n-k,F,2,(n),的解，其中c,1,c,2,c,k,(c,k,0)是实数常数，F,1,(n)与F,1,(n)是只依赖于n且不恒为0的函数，,则,a,n,x(n)y(n)为递推关系,a,n,c,1,a,n-1,c,2,a,n-2,c,k,a,n-k,F,1,(n),F,2,(n),的解,11,3.3.2 举例,例3.3.3,解递归,解,(1),相伴齐次递推关系a,n,3a,n-1,(,),(,)的特征方程x,30,(,)的特征根 x3,(,)的通解a,n,a,3,n,(a为任意常数),12,3.3.2 举例,(2),分别求a,n,3a,n-1,32,n,(,),a,n,3a,n-1,4n,(,),的一个特解,(,),的一个特解形如b2,n,(b为常数),将其代入,(,),得b6,故求得,(,),的一个特解a,n,62,n,类似求得,(,),的一个特解a,n,2n3,故求得()的一个特解a,n,62,n,2n3,13,3.3.2 举例,(3),()的通解,a,n,a3,n,62,n,2n3(a为任意常数),(4),代入a,1,8得a5。故求得递归的解,a,n,53,n,62,n,2n3,14,