組合數(shù)學(xué)幻燈片53

1、5.35.3常系數(shù)線性非常系數(shù)線性非齊次遞歸關(guān)系齊次遞歸關(guān)系 定義定義5.65.6 序列(a0,a1,an,)中相鄰的k+1項(xiàng)之間的關(guān)系 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階常系數(shù)線性非齊次遞歸關(guān)系。其中bi(i=1,2,k)是常數(shù)，且bk0,f(n)0,nk。 定義定義5.75.7 在式(5.18)中，若f(n)=0，則稱 (5.19)(5.19)為由式(5.18)導(dǎo)出的常系數(shù)線性齊次遞歸關(guān)系。knknnnabababa 2211下面的

2、定理指出了常系數(shù)線性非齊次遞歸關(guān)系式(5.18)與由它導(dǎo)出的常系數(shù)線性齊次遞歸關(guān)系式(5.19)的解之間的密切關(guān)系。而 是由式(5.18)導(dǎo)出的齊次線性遞歸關(guān)系式(5.19)的通解。nanikiinqca1*nnnaaa 若 是式(5.18)的一個特解則則是常系數(shù)線性非齊次遞歸關(guān)系式(5.18)的通解。證明：證明：由于 是式(5.19)的通解，故有*na*22*11*knknnnabababa *na)(2211nfabababaknknnn 又由于 是式(5.18)的一個特解，故有由上式可見是式（5.18）的解。)()()()(*222*111*nfaabaabaabaaknknknnnnn

3、n kiniinnnnqcaaaa1* kiniinnnnqcaaaa1*現(xiàn)只需證明將以上二式的兩邊分別相加得能滿足式（5.18）的任意初值條件式（5.14）所導(dǎo)出的關(guān)于c1,c2,ck未知數(shù)的線性方程式組111100, kkhahaha 1122211112211021kkkkkkkkkhcqcqcqhcqcqcqhccc有唯一解即可式中式中)1, 1 , 0( kiahhiii而這是顯然的。因 為 該 方 程 組 的 系 數(shù) 矩 陣 是 一 個VandermondeVandermonde矩陣，其行列式的值不為0。故定理得證。 定理定理5.65.6指出：若要求一個常系數(shù)線性非齊次遞歸關(guān)系式(

4、5.18)的通解，必須先先求出這個遞歸關(guān)系所導(dǎo)出的常系數(shù)線性齊次遞歸關(guān)系式(5.19)的通解，然后再然后再求這個遞歸關(guān)系式(5.18)的一個特解，將其相加即可。然而，求一個非齊次線性遞歸關(guān)系的特解，通常沒有系統(tǒng)的方法，但當(dāng)函數(shù)f(n)是某些特殊形式時，才有一些規(guī)范的求法。下面討論幾種情形： 求解5.1節(jié)例2所導(dǎo)出的“Hanoi塔”問題的遞歸關(guān)系式（5.4)kkknAnAnAa 110 1)2(1211anaann1.1.當(dāng)當(dāng)f(n)f(n)是是n n的的k k次多項(xiàng)式時，次多項(xiàng)式時，a.a.當(dāng)對應(yīng)的齊次特征方程沒有特征根當(dāng)對應(yīng)的齊次特征方程沒有特征根1 1時：時：可設(shè)遞歸關(guān)系式可設(shè)遞歸關(guān)系式(

5、5.18)(5.18)的特解形式為的特解形式為式中A A0 0，A A1 1, ,A,Ak k為待定常數(shù)。解：解：由遞歸關(guān)系式(5.4)導(dǎo)出的齊次線性遞歸關(guān)系 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,故設(shè)式(5.4)的特解為由定理定理5.25.2知，式(5.4)所導(dǎo)出的齊次線性遞歸關(guān)系的通解為將 代入式(5.4)得 A-2A-1=0 A=-1A-2A-1=0 A=-1故故故有 a a=2=2-1-1nnnncaaa21* 11211 cc又由初值條件a1=1可得由定理

6、5.6知，式(5.4)的通解為解：解：由定理5.2易知，上述遞歸關(guān)系所導(dǎo)出的線性齊次遞歸關(guān)系的通解為 3)1(3201annaannnnca)2(*求解遞歸關(guān)系求解遞歸關(guān)系 將上式代入上述遞歸關(guān)系得 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，故設(shè)其特解為比較上式n和常數(shù)項(xiàng)的系數(shù)得 3A0=1,3A1-2A0=3解得 A0=1/3,A1=11/99/113/ nan故故由初值條件a0=3可確定c=16/9。故有nnnncna

7、aa) 2(9/113/* nnna)2(91691131 由定理定理5.65.6知，所求遞歸關(guān)系的通解為值得注意的是，b. b. 當(dāng)常系數(shù)線性非齊次遞歸關(guān)系式(5.18)所導(dǎo)出的常系數(shù)線性齊次常系數(shù)線性齊次遞歸關(guān)系遞歸關(guān)系的特征根有1的m重根時(m1)，特解不能設(shè)為式(5.20)的形式，而這時特解應(yīng)設(shè)為如下形式：式中Ai(i=0,1,k)為待定常數(shù) m1。這是因?yàn)?，如果這時特解仍設(shè)為式(5.20)的形式，則將其特解代入原遞歸關(guān)系時，用待定系數(shù)法確定各Ai將成其為不可能。我們可看下面的例子。mkkknnAnAnAa )(110 解：解：容易求得式(5.10)所導(dǎo)出的齊次遞歸關(guān)系的通解為 2)2

8、()1(211annaannnnca1* 求解遞歸關(guān)系式(5.10)由于 f(n)=2(n-1) 是n的一次多項(xiàng)式。容易驗(yàn)證，若設(shè)其特解為式 （5.20）的形式，則待定系數(shù)求不出來，10AnAan nAnAan)(10 下面求式下面求式（5.10）的特解的特解其原因主要是式（5.10）所導(dǎo)出的線性齊次遞歸關(guān)系的特征根為1。因此，對這種情況必須設(shè)其特解為式（5.21）的形式。故設(shè)其特解為 將 代入式（5.10）得na)1(2)1()1(120120 nnAnAnAnA222010 nAAnA12, 11010 AAAAnnan2化簡得化簡得比較和常數(shù)項(xiàng)的系數(shù)有故故 又由初值條件a1=2可確定c=

9、2。 故式(5.10)的解為 an=n2-n+2cnnaaannn 2*由定理定理5.65.6知，式(5.10)的通解為 2.2. 當(dāng)f(n)是 的形式時，又可分為如下兩種情形：n nnAa (5.22)式中式中A A為待定常數(shù)。為待定常數(shù)。a.a.如果不是常系數(shù)線性非齊次遞歸關(guān)系式(5.18)所導(dǎo)出的常系數(shù)線性齊次遞歸關(guān)系式(5.19)的特征根，可設(shè)特解的形式為 b b. .如果是常系數(shù)線性非齊次遞歸關(guān)系式(5.18)所導(dǎo)出的常系數(shù)線性齊次遞歸關(guān)系式(5.18)的k重特征根時(k1)，可設(shè)特解的形式為nkkknAnAnAa )(110 解：解：由定理定理5.55.5易知遞歸關(guān)系式(5.23)

10、所導(dǎo)出的線性齊次遞歸關(guān)系的通解為nnnnaaa2221 nnncca)1()(21* 求遞歸關(guān)系的通解。(5.23)(5.23) 由于f(n)=2n是n的形式，且=2不是式(5.23)所導(dǎo)出的齊次遞歸關(guān)系的特征根，這屬于情形a a。故設(shè)特解 ，將 代入式(5.23)得nnAa2 nannnnAAA2222221 94 Anna294 解得解得 故有故有 例例5 5 求遞歸關(guān)系 的通解。nnnnnnccaaa) 1)(29421* nnnnaaa24421 由定理定理5.65.6知，式(5.23)的通解為 由于由于f(n)=2f(n)=2n n具有具有n n的形式，且的形式，且=2=2是是二重特征根，這屬于情形二重特征根，這屬于情形b b。故設(shè)特解故設(shè)特解為為 nnncca2)(21* nnAnAnAa2)(2120 解：解：本例與例4的形式大體相同，但在決定特解時有不同之處。由定理5.5易見式(5.24)所導(dǎo)出的線性齊次遞歸關(guān)系的通解為式中2是式(5.24)所導(dǎo)出的線性齊次遞歸關(guān)系的二重特征根。nnAnAAnAnA2)1( 42)(202120 nn