組合數(shù)學(xué)-第四章4常系數(shù)線性非齊次遞推關(guān)系

1、復(fù)習(xí)若q1,q2,qt分別為上述遞推關(guān)系的特征方程C(x)=0相異的m1,m2,mt重特征根， 為該遞推關(guān)系的通解，其中cij由初始條件確定。4,3 常系數(shù)線性齊次相同特征根定理4-2證明：由定理4.4知， 表達式的右端每一項都是遞推關(guān)系an=c1an-1+c2an-2+ckan-k的解。故an也是該遞推關(guān)系的解?，F(xiàn)只需證明該式滿足遞推關(guān)系式an=c1an-1+c2an-2+ckan-k的任意初值條件式a0=d0,a1=d1, ak-1 =dk-1所得的線性方程組有惟一解即可。 將初值條件式a0=d0,a1=d1,ak-1=dk-1代入式(A)得到下列方程組：這個方程組的系數(shù)行列式是Vande

2、rmonde行列式的一個推廣。其行列式之值為故方程組有惟一解。即cij(i=1,2,t; j=1,2,mi)是由初值惟一確定，定理得證。4.3 常系數(shù)線性非齊次定義4.5常系數(shù)線性非齊次遞推關(guān)系定義 4.4若an中相鄰k+1項滿足an+c1an-1+c2an-2+ ckan-k=f(n)，(nk)稱之為an的k階常系數(shù)線性非齊次遞推關(guān)系。其中ci(i=1,2,k)是常數(shù)，且ck0，f(n)0 。若f(n)=0，稱 +c1an-1+c2an-2+ckan-k =0 為上述遞推關(guān)系導(dǎo)出的常系數(shù)線性齊次遞推關(guān)系。4.3 常系數(shù)線性非齊次定理6-34.5 常系數(shù)線性非齊次遞推關(guān)系定理 4.6若 為an

3、+c1an-1+c2an-2+ckan-k=f(n) 的一個特解， 為 =c1an-1+c2an-2+ckan-k 的一個通解，則an= + 為原非齊次遞推關(guān)系的通解。 注：定理4.6指出，若要求一個常系數(shù)線性非齊次遞推關(guān)系式的通解，必須先求出這個遞推關(guān)系所導(dǎo)出的常系數(shù)線性齊次遞推關(guān)系的通解，然后再求這個遞推關(guān)系式的一個特解，將其相加即可。 然而，求一個非齊次線性遞推關(guān)系的特解，通常沒有系統(tǒng)的方法，但當(dāng)函數(shù)f(n)是某些特殊形式時，才有一些規(guī)范的求法。4.3 常系數(shù)線性非齊次定理6-34.5 常系數(shù)線性非齊次遞推關(guān)系定理 4.6若 為an+c1an-1+c2an-2+ckan-k=f(n) 的

4、一個特解， 為 =c1an-1+c2an-2+ckan-k 的一個通解，則an= + 為原非齊次遞推關(guān)系的通解。 證明：由于 是非齊次遞推關(guān)系式導(dǎo)出的齊次線性遞推關(guān)系式即 的通解，故有又由于 是非齊次遞推關(guān)系的一個特解，故有將以上兩式的兩邊分別相加得由上式可見 是式的通解。 若f(n)為n的k次多項式，則 =A0nk+A1nk-1+Ak，其中A0, A1,Ak為待定系數(shù)；若導(dǎo)出的常系數(shù)線性齊次遞推關(guān)系特征根為1的m重根，則 =(A0nk+A1nk-1 +Ak )nm 。4.3 常系數(shù)線性非齊次特殊形式4.5 常系數(shù)線性非齊次遞推關(guān)系 若f(n)為rnb(n)的形式，b(n)是n的p次的多項式若

5、是導(dǎo)出的常系數(shù)線性齊次遞推關(guān)系的m重特征根根，則 =(A0np+A1np-1+Ap)nm r n。4.3 常系數(shù)線性非齊次例14.5 常系數(shù)線性非齊次遞推關(guān)系例 題例1、求遞歸關(guān)系（Hanoi塔） 5.3 常系數(shù)線性非齊次例34.5 常系數(shù)線性非齊次遞推關(guān)系例 題例2、求遞歸關(guān)系 4.3 常系數(shù)線性非齊次例44.5 常系數(shù)線性非齊次遞推關(guān)系例 題例3、求遞歸關(guān)系 an-4an-1+4an-2=2n的通解。4.3 常系數(shù)線性非齊次例44.5 常系數(shù)線性非齊次遞推關(guān)系例 題例4、求遞歸關(guān)系 an+3an-1-10an-2=（5+n)2n的通解。4.3 常系數(shù)線性非齊次例44.5 常系數(shù)線性非齊次遞推關(guān)系練習(xí)求遞歸關(guān)系 的解。4.3 常系數(shù)線性非齊次例74.5 常系數(shù)線性非齊次遞推關(guān)系例 題例5、求Sn=12+