组合数学幻灯片53齐次递归关系课件.ppt

1、5.35.3常系数线性非常系数线性非齐次递归关系齐次递归关系 定义定义5.65.6 序列(a0,a1,an,)中相邻的k+1项之间的关系 a an n=b=b1 1a an-1n-1+b+b2 2a an-2n-2+b+bk ka an-kn-k+f(n)+f(n)(5.18)(5.18)称作序列(a0,a1,an,)的k阶常系数线性非齐次递归关系。其中bi(i=1,2,k)是常数，且bk0,f(n)0,nk。定义定义5.75.7 在式(5.18)中，若f(n)=0，则称 (5.19)(5.19)为由式(5.18)导出的常系数线性齐次递归关系。knknnnabababa 2211下面的定理指出

2、了常系数线性非齐次递归关系式(5.18)与由它导出的常系数线性齐次递归关系式(5.19)的解之间的密切关系。而 是由式(5.18)导出的齐次线性递归关系式(5.19)的通解。nanikiinqca1*nnnaaa 若 是式(5.18)的一个特解则则是常系数线性非齐次递归关系式(5.18)的通解。证明：证明：由于 是式(5.19)的通解，故有*na*22*11*knknnnabababa *na)(2211nfabababaknknnn 又由于 是式(5.18)的一个特解，故有由上式可见是式（5.18）的解。)()()()(*222*111*nfaabaabaabaaknknknnnnnn ki

3、niinnnnqcaaaa1*kiniinnnnqcaaaa1*现只需证明将以上二式的两边分别相加得能满足式（5.18）的任意初值条件式（5.14）所导出的关于c1,c2,ck未知数的线性方程式组111100,kkhahaha 1122211112211021kkkkkkkkkhcqcqcqhcqcqcqhccc有唯一解即可式中式中)1,1,0(kiahhiii而这是显然的。因 为 该 方 程 组 的 系 数 矩 阵 是 一 个VandermondeVandermonde矩阵，其行列式的值不为0。故定理得证。定理定理5.65.6指出：若要求一个常系数线性非齐次递归关系式(5.18)的通解，必须

4、先先求出这个递归关系所导出的常系数线性齐次递归关系式(5.19)的通解，然后再然后再求这个递归关系式(5.18)的一个特解，将其相加即可。然而，求一个非齐次线性递归关系的特解，通常没有系统的方法，但当函数f(n)是某些特殊形式时，才有一些规范的求法。下面讨论几种情形：求解5.1节例2所导出的“Hanoi塔”问题的递归关系式（5.4)kkknAnAnAa 110 1)2(1211anaann1.1.当当f(n)f(n)是是n n的的k k次多项式时，次多项式时，a.a.当对应的齐次特征方程没有特征根当对应的齐次特征方程没有特征根1 1时：时：可设递归关系式可设递归关系式(5.18)(5.18)的

5、特解形式为的特解形式为式中A A0 0，A A1 1,A,Ak k为待定常数。解：解：由递归关系式(5.4)导出的齐次线性递归关系 a an n-2a-2an-1n-1=0=0特征方程为 x-2=0 x-2=0故其特征根为 x x1 1=2=2nnca2*Aan Aan 1 na由于f(n)=1,故设式(5.4)的特解为由定理定理5.25.2知，式(5.4)所导出的齐次线性递归关系的通解为将 代入式(5.4)得 A-2A-1=0 A=-1A-2A-1=0 A=-1故故故有 a a=2=2-1-1nnnncaaa21*11211 cc又由初值条件a1=1可得由定理5.6知，式(5.4)的通解为解

6、：解：由定理5.2易知，上述递归关系所导出的线性齐次递归关系的通解为 3)1(3201annaannnnca)2(*求解递归关系求解递归关系 将上式代入上述递归关系得 A A0 0n+An+A1 1+2+2A A0 0(n-1)+A(n-1)+A1 1=n+3=n+3化简得 3A3A0 0n+3An+3A1 1-2A-2A0 0=n+3=n+310AnAan 由于f(n)=n+3，故设其特解为比较上式n和常数项的系数得 3A0=1,3A1-2A0=3解得 A0=1/3,A1=11/99/113/nan故故由初值条件a0=3可确定c=16/9。故有nnnncnaaa)2(9/113/*nnna)

7、2(91691131 由定理定理5.65.6知，所求递归关系的通解为值得注意的是，b.b.当常系数线性非齐次递归关系式(5.18)所导出的常系数线性齐次常系数线性齐次递归关系递归关系的特征根有1的m重根时(m1)，特解不能设为式(5.20)的形式，而这时特解应设为如下形式：式中Ai(i=0,1,k)为待定常数 m1。这是因为，如果这时特解仍设为式(5.20)的形式，则将其特解代入原递归关系时，用待定系数法确定各Ai将成其为不可能。我们可看下面的例子。mkkknnAnAnAa )(110 解：解：容易求得式(5.10)所导出的齐次递归关系的通解为 2)2()1(211annaannnnca1*求

8、解递归关系式(5.10)由于 f(n)=2(n-1)是n的一次多项式。容易验证，若设其特解为式 （5.20）的形式，则待定系数求不出来，10AnAan nAnAan)(10 下面求式下面求式（5.10）的特解的特解其原因主要是式（5.10）所导出的线性齐次递归关系的特征根为1。因此，对这种情况必须设其特解为式（5.21）的形式。故设其特解为 将 代入式（5.10）得na)1(2)1()1(120120 nnAnAnAnA222010 nAAnA12,11010 AAAAnnan2化简得化简得比较和常数项的系数有故故 又由初值条件a1=2可确定c=2。故式(5.10)的解为 an=n2-n+2c

9、nnaaannn 2*由定理定理5.65.6知，式(5.10)的通解为 2.2.当f(n)是 的形式时，又可分为如下两种情形：n nnAa (5.22)式中式中A A为待定常数。为待定常数。a.a.如果不是常系数线性非齐次递归关系式(5.18)所导出的常系数线性齐次递归关系式(5.19)的特征根，可设特解的形式为 b b.如果是常系数线性非齐次递归关系式(5.18)所导出的常系数线性齐次递归关系式(5.18)的k重特征根时(k1)，可设特解的形式为nkkknAnAnAa)(110 解：解：由定理定理5.55.5易知递归关系式(5.23)所导出的线性齐次递归关系的通解为nnnnaaa2221 n

10、nncca)1()(21*求递归关系的通解。(5.23)(5.23)由于f(n)=2n是n的形式，且=2不是式(5.23)所导出的齐次递归关系的特征根，这属于情形a a。故设特解 ，将 代入式(5.23)得nnAa2 nannnnAAA2222221 94 Anna294 解得解得 故有故有 例例5 5 求递归关系 的通解。nnnnnnccaaa)1)(29421*nnnnaaa24421 由定理定理5.65.6知，式(5.23)的通解为 由于由于f(n)=2f(n)=2n n具有具有n n的形式，且的形式，且=2=2是是二重特征根，这属于情形二重特征根，这属于情形b b。故设特解故设特解为为

11、 nnncca2)(21*nnAnAnAa2)(2120 解：解：本例与例4的形式大体相同，但在决定特解时有不同之处。由定理5.5易见式(5.24)所导出的线性齐次递归关系的通解为式中2是式(5.24)所导出的线性齐次递归关系的二重特征根。nnAnAAnAnA2)1(42)(202120 nnAnAnA22)2()2(422120 2/122200 AAnnnnAnAna2)2/(212 将特解代入式得整理化简得整理化简得故故由定理定理5.65.6知，式(5.24)的通解为*nnnaaa nnnccAnAn2)(2)2/(21212 nnncncn2222112 211cAc 122cAc 式中，和 由初值条件确定。