组合数学-第四章4常系数线性非齐次递推关系

1、复习若q1,q2,qt分别为上述递推关系的特征方程C(x)=0相异的m1,m2,mt重特征根， 为该递推关系的通解，其中cij由初始条件确定。4,3 常系数线性齐次相同特征根定理4-2证明：由定理4.4知， 表达式的右端每一项都是递推关系an=c1an-1+c2an-2+ckan-k的解。故an也是该递推关系的解。现只需证明该式满足递推关系式an=c1an-1+c2an-2+ckan-k的任意初值条件式a0=d0,a1=d1, ak-1 =dk-1所得的线性方程组有惟一解即可。 将初值条件式a0=d0,a1=d1,ak-1=dk-1代入式(A)得到下列方程组：这个方程组的系数行列式是Vande

2、rmonde行列式的一个推广。其行列式之值为故方程组有惟一解。即cij(i=1,2,t; j=1,2,mi)是由初值惟一确定，定理得证。4.3 常系数线性非齐次定义4.5常系数线性非齐次递推关系定义 4.4若an中相邻k+1项满足an+c1an-1+c2an-2+ ckan-k=f(n)，(nk)称之为an的k阶常系数线性非齐次递推关系。其中ci(i=1,2,k)是常数，且ck0，f(n)0 。若f(n)=0，称 +c1an-1+c2an-2+ckan-k =0 为上述递推关系导出的常系数线性齐次递推关系。4.3 常系数线性非齐次定理6-34.5 常系数线性非齐次递推关系定理 4.6若 为an

3、+c1an-1+c2an-2+ckan-k=f(n) 的一个特解， 为 =c1an-1+c2an-2+ckan-k 的一个通解，则an= + 为原非齐次递推关系的通解。 注：定理4.6指出，若要求一个常系数线性非齐次递推关系式的通解，必须先求出这个递推关系所导出的常系数线性齐次递推关系的通解，然后再求这个递推关系式的一个特解，将其相加即可。 然而，求一个非齐次线性递推关系的特解，通常没有系统的方法，但当函数f(n)是某些特殊形式时，才有一些规范的求法。4.3 常系数线性非齐次定理6-34.5 常系数线性非齐次递推关系定理 4.6若 为an+c1an-1+c2an-2+ckan-k=f(n) 的

4、一个特解， 为 =c1an-1+c2an-2+ckan-k 的一个通解，则an= + 为原非齐次递推关系的通解。 证明：由于 是非齐次递推关系式导出的齐次线性递推关系式即 的通解，故有又由于 是非齐次递推关系的一个特解，故有将以上两式的两边分别相加得由上式可见 是式的通解。 若f(n)为n的k次多项式，则 =A0nk+A1nk-1+Ak，其中A0, A1,Ak为待定系数；若导出的常系数线性齐次递推关系特征根为1的m重根，则 =(A0nk+A1nk-1 +Ak )nm 。4.3 常系数线性非齐次特殊形式4.5 常系数线性非齐次递推关系 若f(n)为rnb(n)的形式，b(n)是n的p次的多项式若

5、是导出的常系数线性齐次递推关系的m重特征根根，则 =(A0np+A1np-1+Ap)nm r n。4.3 常系数线性非齐次例14.5 常系数线性非齐次递推关系例 题例1、求递归关系（Hanoi塔） 5.3 常系数线性非齐次例34.5 常系数线性非齐次递推关系例 题例2、求递归关系 4.3 常系数线性非齐次例44.5 常系数线性非齐次递推关系例 题例3、求递归关系 an-4an-1+4an-2=2n的通解。4.3 常系数线性非齐次例44.5 常系数线性非齐次递推关系例 题例4、求递归关系 an+3an-1-10an-2=（5+n)2n的通解。4.3 常系数线性非齐次例44.5 常系数线性非齐次递推关系练习求递归关系 的解。4.3 常系数线性非齐次例74.5 常系数线性非齐次递推关系例 题例5、求Sn=12+