组合数学幻灯片53..ppt

§5.3 常系数线性非齐次递归关系 定义5.6 序列(a0,a1,…,an,…)中相邻的k+1项之间的关系 an=b1an-1+b2an-2+…+bkan-k+f(n) (5.18) 称作序列(a0,a1,…,an,…)的k阶常系数线性非齐次递归关系。 其中bi(i=1,2,…,k)是常数，且bk≠0,f(n)≠0,n≥k。 定义5.7 在式(5.18)中，若f(n)=0，则称 (5.19) 为由式(5.18)导出的常系数线性齐次递归关系。  下面的定理指出了常系数线性非齐次递归关系式(5.18)与由它导出的常系数线性齐次递归关系式(5.19)的解之间的密切关系。 而 是由式(5.18)导出的齐次 线性递归关系式(5.19)的通解。 若 是式(5.18)的一个特解 则 是常系数线性非齐次递归关系式(5.18)的通解。 证明：由于 是式(5.19)的通解，故有 又由于 是式(5.18)的一个特解，故有 由上式可见 是式（5.18）的解。 现只需证明 将以上二式的两边分别相加得 能满足式（5.18）的任意初值条件式（5.14） 所导出的关于c1,c2,…,ck未知数的线性方程式组 有唯一解即可 式中 而这是显然的。 因为该方程组的系数矩阵是一个Vandermonde矩阵，其行列式的值不为0。故定理得证。 定理5.6指出： 若要求一个常系数线性非齐次递归关系式(5.18)的通解，必须先求出这个递归关系所导出的常系数线性齐次递归关系式(5.19)的通解，然后再求这个递归关系式(5.18)的一个特解，将其相加即可。 然而，求一个非齐次线性递归关系的特解，通常没有系统的方法，但当函数f(n)是某些特殊形式时，才有一些规范的求法。下面讨论几种情形： 求解§5.1节例2所导出的“Hanoi塔”问题的递归关系式（5.4) 1.当f(n)是n的k次多项式时， a.当对应的齐次特征方程没有特征根1时： 可设递归关系式(5.18)的特解形式为 式中A0，A1,…,Ak为待定常数。 解：由递归关系式(5.4)导出的齐次线性递归关系 an-2an-1=0 特征方程为 x-2=0 故其特征根为 x1=2  由于f(n)=1,故设式(5.4)的特解为 由定理5.2知，式(5.4)所导出的齐次线性递归关系的通解为 将 代入式(5.4)得 A-2A-1=0 A=-1 故 故有 aｎ=2ｎ-1 又由初值条件a1=1可得 由定理5.6知，式(5.4)的通解为 解：由定理5.2易知，上述递归关系所导出的线性齐次递归关系的通解为 求解递归关系 将上式代入上述递归关系得 A0·n+A1+2［A0(n-1)+A1］=n+3 化简得 3A0·n+3A1-2A0=n+3 由于f(n)=n+3，故设其特解为 比较上式n和常数项的系数得 3A0=1,3A1-2A0=3 解得 A0=1/3,A1=11/9 故 由初值条件a0=3可确定c=16/9。 故有 由定理5.6知，所求递归关系的通解为 值得注意的是，b. 当常系数线性非齐次递归关系式(5.18)所导出的常系数线性齐次递归关系的特征根有1的m重根时(m≥1)， 特解不能设为式(5.20)的形式，而这时特解应设为如下形式： 式中Ai(i=0,1,…,k)为待定常数 m≥1。 这是因为，如果这时特解仍设为式(5.20)的形式，则将其特解代入原递归关系时，用待定系数法确定各Ai将成其为不可能。我们可看下面的例子。 解：容易求得式(5.10)所导出的齐次递归关系的通解为 求解递归关系式(5.10) 由于 f(n)=2(n-1) 是n的一次多项式。容易验证，若设其特解为式 （5.20）的形式，则待定系数求不出来， 下面求式（5.10）的特解 其原因主要是式（5.10）所导出的线性齐次递归关系的特征根为1。 因此，对这种情况必须设其特解为式（5.21）的形式。故设其特解为 将 代入式（5.10）得 化简得 比较和常数项的系数有 故 又由初值条件a1=2可确定c=2。 故式(5.10)的解为  an=n2-n+2 由定理5.6知，式(5.10)的通解为 2. 当f(n)是 的形式时，又可分为如下两种情形： (5.22) 式中A为待定常数。 a.如果β不是常系数线性非齐次递归关系式(5.18)所导出的常系数线性齐次递归关系式(5.19)的特征根，可设特