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

1、4.4 線性常系數(shù)齊次遞推關(guān)系 4.4 線性常系數(shù)齊次遞推關(guān)系 定義 如果序列 滿足 及 是常數(shù)， ，則稱(chēng)為 的 階常系數(shù)線性齊次遞推關(guān)， 稱(chēng)為 的初始條件，稱(chēng)為 的特征多項(xiàng)式4.4 線性常系數(shù)齊次遞推關(guān)系 設(shè) 為 的母函數(shù)，有4.4 線性常系數(shù)齊次遞推關(guān)系將這些式子兩邊分別相加，得到即其中4.4 線性常系數(shù)齊次遞推關(guān)系 令 ，多項(xiàng)式 的次數(shù)不大于 。特征多項(xiàng)式4.4 線性常系數(shù)齊次遞推關(guān)系因此，是 次多項(xiàng)式，我們知道 在復(fù)數(shù)域中有 個(gè)根。設(shè)4.4 線性常系數(shù)齊次遞推關(guān)系則 于是4.4 線性常系數(shù)齊次遞推關(guān)系式是有理式，且分子的次數(shù)低于分母的次數(shù)，有分項(xiàng)表示，即：4.4 線性常系數(shù)齊次遞推關(guān)系

2、承上頁(yè)： 的系數(shù)是 。 是常數(shù)。4.4 線性常系數(shù)齊次遞推關(guān)系以下分別各種情況討論具體計(jì)算的問(wèn)題。（1）特征多項(xiàng)式 無(wú)重根 設(shè) 可見(jiàn)化為4.4 線性常系數(shù)齊次遞推關(guān)系 的系數(shù)是可由線性方程組解出。例1、求遞歸關(guān)系 4.4 常系數(shù)線性齊次例14.4 常系數(shù)線性齊次遞推關(guān)系4.3.1 相異特征根的解法 例 題4.4 常系數(shù)線性齊次例24.4 常系數(shù)線性齊次遞推關(guān)系4.4.1 相異特征根的解法 例 題例2、求遞歸關(guān)系 4.4 常系數(shù)線性齊次相同特征根定理4-14.4 常系數(shù)線性齊次遞推關(guān)系4.4.2 相同特征根的解法 定理 4.5若q1,q2,qt分別為上述遞推關(guān)系的特征方程C(x)=0相異的m1,

3、m2,mt重特征根， 為該遞推關(guān)系的通解，其中cij由初始條件確定。4.4 常系數(shù)線性齊次相同特征根定理4-24.4 常系數(shù)線性齊次遞推關(guān)系4.3.2 相同特征根的解法 證明：由定理4.4知， 表達(dá)式的右端每一項(xiàng)都是遞推關(guān)系an=b1an-1+b2an-2+bkan-k的解。故an也是該遞推關(guān)系的解?，F(xiàn)只需證明該式滿足遞推關(guān)系式an=b1an-1+b2an-2+bkan-k的任意初值條件式a0=d0,a1=d1, ak-1 =dk-1所得的線性方程組有惟一解即可。 將初值條件式a0=d0,a1=d1,ak-1=dk-1代入式(A)得到下列方程組：這個(gè)方程組的系數(shù)行列式是Vandermonde行

4、列式的一個(gè)推廣。其行列式之值為故方程組有惟一解。即cij(i=1,2,t; j=1,2,mi)是由初值惟一確定，定理得證。例3、求遞歸關(guān)系 4.4 常系數(shù)線性齊次例34.4 常系數(shù)線性齊次遞推關(guān)系4.4.2 相同特征根的解法 例 題例4、求遞歸關(guān)系 4.4 常系數(shù)線性齊次例44.4 常系數(shù)線性齊次遞推關(guān)系4.3.2 相同特征根的解法 例 題4.4 常系數(shù)線性齊次例54.4 常系數(shù)線性齊次遞推關(guān)系4.3.2 相同特征根的解法 例 題例5、求遞歸關(guān)系4.4 常系數(shù)線性齊次例64.4 常系數(shù)線性齊次遞推關(guān)系4.3.2 相同特征根的解法 例 題例6、計(jì)算n階行列式的值：解：設(shè)具有以上形式的n階行列式的值為