線性常系數(shù)齊次遞推關(guān)系

1、2.3 線性常系數(shù)齊次遞推關(guān)系線性常系數(shù)齊次遞推關(guān)系主講教師主講教師 數(shù)學(xué)學(xué)院魏毅強教授數(shù)學(xué)學(xué)院魏毅強教授聯(lián)系電話聯(lián)系電話Email : Yiqiang Wei 22.3 線性常系數(shù)齊次遞推關(guān)系線性常系數(shù)齊次遞推關(guān)系2.3.1 定義定義定義定義2.3.1 形如形如 an+c1an-1+c2an-2+ckan-k=0, (nk-1)( (其中其中c1,c2,ck是常數(shù)，是常數(shù)，ck0，k是正整數(shù)是正整數(shù)) )的遞推關(guān)系稱的遞推關(guān)系稱為為k k階線性常系數(shù)齊次遞推關(guān)系階線性常系數(shù)齊次遞推關(guān)系。稱稱a0=d0，a1=d1，ak-1=dk-1 為為初值條件初值條件。例如例如

2、Fibonacci數(shù)列數(shù)列滿足滿足Fn-Fn-1-Fn-2=0，(n2)為為2 2階線性常階線性常系數(shù)齊次遞推關(guān)系。系數(shù)齊次遞推關(guān)系。an-3an-1-2an-2+4an-3=0 是三階線性常系數(shù)齊次遞推關(guān)系是三階線性常系數(shù)齊次遞推關(guān)系例如，例如，an+3an-1+2an-2=0 是二階線性常系數(shù)齊次遞推關(guān)系是二階線性常系數(shù)齊次遞推關(guān)系Yiqiang Wei 32.3 線性常系數(shù)齊次遞推關(guān)系線性常系數(shù)齊次遞推關(guān)系定義定義2.3.2 給定給定k k階線性常系數(shù)齊次遞推關(guān)系階線性常系數(shù)齊次遞推關(guān)系an+c1an-1+c2an-2+ckan-k=0, (ck0，nk-1)記記 C(x)=xk+c1x

3、k-1+c2xk-2+ck 稱稱為線性常系數(shù)齊次遞推關(guān)為線性常系數(shù)齊次遞推關(guān)系的系的特征多項式特征多項式，而稱，而稱 C(x)=0 為為特征方程特征方程。例如例如 Fibonacci數(shù)列數(shù)列所滿足的所滿足的2 2階線性常系數(shù)齊次遞推關(guān)系階線性常系數(shù)齊次遞推關(guān)系 Fn-Fn-1-Fn-2=0，(n2)的特征方程的特征方程為為x2-x-1=0。例如，例如，an+3an-1+2an-2=0 的特征多項式為的特征多項式為 x2+3x+2=0 an-3an-1-2an-2+4an-3=0 的特征多項式為的特征多項式為 x3-3x2-2x+4=0Yiqiang Wei 4根據(jù)遞推關(guān)系，有根據(jù)遞推關(guān)系，有0

4、)(0)(0)(221111211102211knknnnnkkkkkkkkkkacacacaxacacacaxacacacax2.3.2 線性常系數(shù)齊次遞推關(guān)系的母函數(shù)方法線性常系數(shù)齊次遞推關(guān)系的母函數(shù)方法設(shè)設(shè) an的母函數(shù)為的母函數(shù)為G(x)nnxaxaaxG10)(02211knknnnacacaca設(shè)設(shè)an滿足滿足k階線性常系數(shù)齊次遞推關(guān)系階線性常系數(shù)齊次遞推關(guān)系2.3 線性常系數(shù)齊次遞推關(guān)系線性常系數(shù)齊次遞推關(guān)系Yiqiang Wei 5將這些式子兩邊分別相加，得到將這些式子兩邊分別相加，得到 010201xGxCxaxGxCxaxGkkkikiiiii即即 10102211kjjk

5、iiijjkkxaxCxGxCxCxC其中其中 C0=1令令 10100kjjkiiijjxaxCxP為次數(shù)不超過為次數(shù)不超過k-1的多項式的多項式 kkkCxCxxC 11也稱為特征多項式也稱為特征多項式由于，由于，kkkxCxCxCx 1112.3 線性常系數(shù)齊次遞推關(guān)系線性常系數(shù)齊次遞推關(guān)系Yiqiang Wei 6如果如果C(x)=0 在復(fù)數(shù)域中有在復(fù)數(shù)域中有k個根。設(shè)個根。設(shè) kkkkxxxxCskskks212121則則 skskkkkkxxxxCxCxCx1111121211于是于是)()(101xPxGxCxCkk 111)()(21210skskkxxxxPxG2.3 線性常

6、系數(shù)齊次遞推關(guān)系線性常系數(shù)齊次遞推關(guān)系Yiqiang Wei 7上式是有理式，且分子的次數(shù)低于分母的次數(shù)，是真分上式是有理式，且分子的次數(shù)低于分母的次數(shù)，是真分式，可分項表示為：式，可分項表示為：ttkitkititkkkkxAxAxAxAxAxAxAxAxAxG)1 ()1 (1 )1 ()1 (1 )1 ()1 (1)(2212222222211121121112211其中其中Ast,s=1,2,i; t=1,2,ks為待定常數(shù)為待定常數(shù)2.3 線性常系數(shù)齊次遞推關(guān)系線性常系數(shù)齊次遞推關(guān)系Yiqiang Wei 802)(1()1 (1jjxjx注意到注意到0)(11jjxx03)(1)(

7、2()1 (2jjxjjx！01)(1() 1)()1 (jjkxjkjkjxk！一般地一般地2.3 線性常系數(shù)齊次遞推關(guān)系線性常系數(shù)齊次遞推關(guān)系Yiqiang Wei 9于是于是111)1 ()(nnniskttsstxaxAxGinsissnsisktstnBnntAas111 1其中其中xn的系數(shù)的系數(shù)其中其中Bs為待定系數(shù)，由初值條件唯一確定為待定系數(shù)，由初值條件唯一確定2.3 線性常系數(shù)齊次遞推關(guān)系線性常系數(shù)齊次遞推關(guān)系Yiqiang Wei 10例例2.3.1 求求an-an-1-6an-2=0 , a0=5, a1=3 的解的解 設(shè)母函數(shù)為設(shè)母函數(shù)為 解解 0)(nnnxaxG代

8、入遞推關(guān)系有代入遞推關(guān)系有 22110)6()(nnnnxaaxaaxG021635nnnnnnxaxxaxx)(6)5)(352xGxxGxxxxGxx25)()61 (22.3 線性常系數(shù)齊次遞推關(guān)系線性常系數(shù)齊次遞推關(guān)系Yiqiang Wei 11)21)(31 (25)(xxxxGxx2151231513 00)2(512)3(513 kkkkxxnnnnx)2(5123513( 0所求解為所求解為 0,)2(5123513a nnnn2.3 線性常系數(shù)齊次遞推關(guān)系線性常系數(shù)齊次遞推關(guān)系Yiqiang Wei 12例例2.3.2 求求an-4an-1+4an-2=0 , a0=1, a

9、1=3 的解的解 設(shè)母函數(shù)為設(shè)母函數(shù)為 解解 0)(nnnxaxG代入遞推關(guān)系有代入遞推關(guān)系有 22110)44()(nnnnxaaxaaxG0204)1(431nnnnnnxaxxaxx)(4)(412xGxxxGxxxGxx1)()441 (22.3 線性常系數(shù)齊次遞推關(guān)系線性常系數(shù)齊次遞推關(guān)系Yiqiang Wei 132)21 (1)(xxxG2)21 (212121xx00)2)(1(21)2(21 kkkkxkxnnnxn02)2(21 所求解為所求解為 0,2)2(21a nnnn2.3 線性常系數(shù)齊次遞推關(guān)系線性常系數(shù)齊次遞推關(guān)系Yiqiang Wei 142.3 線性常系數(shù)齊

10、次遞推關(guān)系線性常系數(shù)齊次遞推關(guān)系2.3.3 線性常系數(shù)齊次遞推關(guān)系的特征根方法線性常系數(shù)齊次遞推關(guān)系的特征根方法02211knknnnacacaca由母函數(shù)方法可知由母函數(shù)方法可知k階線性常系數(shù)齊次遞推關(guān)系階線性常系數(shù)齊次遞推關(guān)系nsissnsisktstnnBnntAas 111)( 1的解可表示為的解可表示為其中其中Bs(n)為待定系數(shù)的為待定系數(shù)的n的的ks-1次多項式次多項式，由初值條件唯，由初值條件唯一確定一確定其中其中i 是特征方程是特征方程 C(x)=xk+c1xk-1+c2xk-2+ck=0 的的ki重重特征根特征根Yiqiang Wei 15以下分別各種情況討論具體計算的問題

11、。以下分別各種情況討論具體計算的問題。 特征多項式無重根特征多項式無重根 kxxxxC21 011221111111nnkiniikiiikkxAxAxAxAxAxG則則kiniinAa1比較系數(shù)得比較系數(shù)得2.3 線性常系數(shù)齊次遞推關(guān)系線性常系數(shù)齊次遞推關(guān)系Yiqiang Wei 161112211112211021kkkkkkkkkdAAAdAAAdAAA其中其中Aij為待定系數(shù)可由以下線性方程組解得為待定系數(shù)可由以下線性方程組解得由于系數(shù)矩陣的行列式是由于系數(shù)矩陣的行列式是Vandermond 行列式，所以方程行列式，所以方程組有唯一解組有唯一解2.3 線性常系數(shù)齊次遞推關(guān)系線性常系數(shù)齊

12、次遞推關(guān)系Yiqiang Wei 17例例2.3.3 求求an-an-1-12an-2=0 , a0=3, a1=26 的解的解 特征方程特征方程 x2-x-12=0根為根為: : x=4 x=-3故通解為故通解為0,) 3(421nAAannn解解由初值條件由初值條件213AA ) 3(42621AA解得解得51A2 -2A所求解為所求解為0,) 3(245nannn2.3 線性常系數(shù)齊次遞推關(guān)系線性常系數(shù)齊次遞推關(guān)系Yiqiang Wei 18)sin(cos,sincos121iaaia則則xn的系數(shù)是的系數(shù)是特征多項式有共軛復(fù)根特征多項式有共軛復(fù)根設(shè)設(shè)1 1與與2 2是一對共軛復(fù)根，設(shè)

13、是一對共軛復(fù)根，設(shè)nBnAnAAinAAninAninAiAiAAAnnnnnnnnnnnnsincossin)(cos)()sin(cos)sin(cos)sin(cos)sin(cos2121212122112.3 線性常系數(shù)齊次遞推關(guān)系線性常系數(shù)齊次遞推關(guān)系Yiqiang Wei 19其中其中3sin3cos2321ii)( ,2121AAiBAAA在具體計算時，可先求出各對共軛復(fù)根，再求待定系數(shù)在具體計算時，可先求出各對共軛復(fù)根，再求待定系數(shù)A，B，避免中間過程的復(fù)數(shù)運算。，避免中間過程的復(fù)數(shù)運算。例例2.3.4 求求an-an-1+an-2=0 , a0=1, a1=1 的解的解 特

14、征方程特征方程 2-+1=0解解根為根為: :故通解為故通解為3sin3cos2211nBnAAAannn2.3 線性常系數(shù)齊次遞推關(guān)系線性常系數(shù)齊次遞推關(guān)系Yiqiang Wei 20由初值條件由初值條件A123211BA解得解得1A31B所求解為所求解為3sin313cosnnan2.3 線性常系數(shù)齊次遞推關(guān)系線性常系數(shù)齊次遞推關(guān)系Yiqiang Wei 21特征多項式有重根特征多項式有重根設(shè)設(shè)是是C(x)=0的的k重根，則由母函數(shù)方法，簡化后含有重根，則由母函數(shù)方法，簡化后含有kiiixA1)1 (11)1 (nnnkiiixaxAnkknkiinnBnBBnniAa)( 111101其

15、中其中xn的系數(shù)的系數(shù)其中其中Bi為待定系數(shù)，由初值條件唯一確定為待定系數(shù)，由初值條件唯一確定2.3 線性常系數(shù)齊次遞推關(guān)系線性常系數(shù)齊次遞推關(guān)系Yiqiang Wei 22例例2.3.5 求下列求下列n階行列式的值。階行列式的值。20012100012100012nd解解根據(jù)行列式性質(zhì)根據(jù)行列式性質(zhì), ,按第一行展開按第一行展開 221nnnddd3 , 221dd并且有初值并且有初值2.3 線性常系數(shù)齊次遞推關(guān)系線性常系數(shù)齊次遞推關(guān)系Yiqiang Wei 23問題變成線性常系數(shù)齊次遞推關(guān)系問題變成線性常系數(shù)齊次遞推關(guān)系3 , 2022121dddddnnn特征方程特征方程 x2-2x+1

16、=0解得解得 x=1 為二重根為二重根故通解為故通解為1,12121nnAAnAAdnn）（由初值條件由初值條件212AA 2321AA 解得解得11A12A所求解為所求解為1,1nndn2.3 線性常系數(shù)齊次遞推關(guān)系線性常系數(shù)齊次遞推關(guān)系Yiqiang Wei 24總之：總之：nkknnBnBBa)(1110若若是是特征方程特征方程C(x)=0的單根，則遞推關(guān)系的解中含有項的單根，則遞推關(guān)系的解中含有項nnaaA若若是特征方程是特征方程C(x)=0的的k重根，則遞推關(guān)系的解中含有項重根，則遞推關(guān)系的解中含有項若若1 1, ,2 2是一對是一對k k重共軛復(fù)根，且重共軛復(fù)根，且)sin(cos

17、12iaa則遞推關(guān)系的解中含有項則遞推關(guān)系的解中含有項nnCnCCnnBnBBankknkknsin)(cos)(111011102.3 線性常系數(shù)齊次遞推關(guān)系線性常系數(shù)齊次遞推關(guān)系Yiqiang Wei 252.3 線性常系數(shù)齊次遞推關(guān)系線性常系數(shù)齊次遞推關(guān)系例例2.3.6 求求12321nnnSSSnknkS01321 1321 1nSnnSnnnSSnn1 同理同理121nSSnn相減得相減得1221nnnSSS同理同理再相減得再相減得033321nnnnSSSSYiqiang Wei 26所以，得到遞推關(guān)系所以，得到遞推關(guān)系 3 , 1 , 0 033 210321SSSSSSSnnn

18、n對應(yīng)的特征方程為對應(yīng)的特征方程為0) 1(133323mmmm2.3 線性常系數(shù)齊次遞推關(guān)系線性常系數(shù)齊次遞推關(guān)系m=1是三重根，故通解為是三重根，故通解為22) 1)(CnBnACnBnASnnYiqiang Wei 270 , 00AS1 , 11CBS21 , 342 , 32CBCBS即即) 1(2121212nnnnSn) 1(21321nnn這就證明了這就證明了2.3 線性常系數(shù)齊次遞推關(guān)系線性常系數(shù)齊次遞推關(guān)系由初值條件，得由初值條件，得Yiqiang Wei 28 Yiqiang Wei 29例例2 2：求nknkS0222212222) 1(321 ) 1(321 nSnn

19、Snn21 nSSnn同理221) 1( nSSnn相減得12221nSSSnnn2.3 線性常系數(shù)齊次遞推關(guān)系線性常系數(shù)齊次遞推關(guān)系Yiqiang Wei 30同理1) 1(22321nSSSnnn 14 , 5 , 1 , 0 0464 32104321SSSSSSSSSnnnnn對應(yīng)的特征方程為0) 1(1464014644234234rrrrrmmmm相減得233321nnnnSSSS同理2334321nnnnSSSS2.3 2.3 線性遞推關(guān)系線性遞推關(guān)系Yiqiang Wei 31 是四重根1rnnDnCnBnAS) 1)( 32依據(jù) 得關(guān)于A、B、C、D的連立方程組：14, 5,

20、 1, 03210SSSS142793584210DCBDCBDCBA2.3 2.3 線性遞推關(guān)系線性遞推關(guān)系Yiqiang Wei 32122793842111612791484511121B2.3 2.3 線性遞推關(guān)系線性遞推關(guān)系Yiqiang Wei 33 已知 是n的3次式，故不妨令nS)2)(1(! 31) 1(! 21nnDnnCnBnASn確定待定系數(shù)時，比較方便，無需解一聯(lián)立方程組。 例如0 , 00ASn時1 , 1 , 11BBASn時3 , 52 , 22CCBSn時2 ,1433 , 33DDCBSn時2.3 2.3 線性遞推關(guān)系線性遞推關(guān)系Yiqiang Wei 34) 12)(1(61 )2)(1(31) 1(23 nnnnnnnnnSn2.3 2.3 線性遞推關(guān)系線性遞推關(guān)系Yiqiang Wei 35 例例4 4：求33321nSn 解解: : 是n的3次多項式，因此 是滿足遞推關(guān)系：31) 1( nSSSnnnnS051010554321nnnnnnSSSSSS設(shè)43214321nAnAnAnASn2.3 2.3 線性遞推關(guān)系線性遞推關(guān)系Yiqiang Wei 366 ,412674110043612 ,2373136397 ,121921144343333223