全文字?jǐn)?shù):3283

遞推關(guān)系的解法研究

 [摘 要] 遞推關(guān)系是組合論中的重要內(nèi)容，幾乎在一切數(shù)學(xué)分支中都有應(yīng)用，如何解遞推關(guān)系，又是遞推關(guān)系中的重要問題，事實(shí)上并沒有一般法則能使我們解出所有的遞推關(guān)系，我們只是對(duì)極少數(shù)的幾類遞推關(guān)系得到一般解法。遞推關(guān)系可以用普通的迭加方法，公式法以及生成函數(shù)法研究。
[關(guān)鍵詞] 遞推關(guān)系、斐波那契遞歸、線性齊次遞推關(guān)系、非齊次遞推關(guān)系、生成函數(shù)
 遞推關(guān)系是組合論中的重要內(nèi)容，幾乎在一切數(shù)學(xué)分支中都有應(yīng)用，如何解遞推關(guān)系，又是遞推關(guān)系中的重要問題，事實(shí)上并沒有一般法則能使我們解出所有的遞推關(guān)系，一、簡單的遞推關(guān)系：
算術(shù)序列，hn=hn-1+q.
幾何序列，hn=h（n-1）q.
可以用普通的迭加方法
滿足遞推關(guān)系和初始條件
          fn=fn-1+ fn-2        (n≥2)
          f0=0, f1=1
  的數(shù)列 f0, f1,f2,f3,…叫做斐波那契序列，序列的項(xiàng)叫做斐波那契數(shù)，式中的遞推關(guān)系叫做斐波那契遞歸。
現(xiàn)在的目標(biāo)是得到斐波那契數(shù)的公式，并為此敘述求解遞推關(guān)系的技巧, 考慮在形式
         Fn－fn-1－fn-2=0  (n≥2)
下斐波那契遞推關(guān)系，先忽略f0 和f1的初始值。解決這個(gè)遞推關(guān)系的一種方法是尋找形式為 fn=qn
   的一個(gè)解，其中q是一個(gè)非零數(shù)。因此，在第一項(xiàng)等于q0=1 的幾何序列種尋找一個(gè)解。我們觀察到，fn=qn滿足斐波那契遞推關(guān)系當(dāng)且僅當(dāng)
        qn－qn-1－qn-2＝0
 或等價(jià)地
        qn-2(q2－q－1)=0   (n=2,3,4,......)
由于假設(shè)q異于零，我們斷言fn=qn是斐波那契遞推關(guān)系的解當(dāng)且僅當(dāng)q2－q－1=0
和
兩者都是斐波那契遞推關(guān)系的解。由于斐波那契遞推關(guān)系是線性的和齊次的。通過直接計(jì)算得到

對(duì)于任意選擇的常數(shù)和，上式也是遞推關(guān)系的解

二、線性齊次遞推關(guān)系
令
         h0,h1,h2,…,hn,…                       (1)
是一個(gè)數(shù)列。如果存在量A1,a2,…,ak, ak≠0和量bn(每一個(gè)量都可能依賴于n)的
   hn=a1hn-1+a2hn-2+…+akhn-k+bn(n≥k)             (2)
則稱該數(shù)列滿足k階線性遞推關(guān)系.
解常系數(shù)線性齊次遞推關(guān)系，即如
     hn=a1hn-1+a2hn-2+…+akhn-k   (n≥k)            (3)
其中A1,a2,…,ak是常數(shù)且ak≠0的遞推關(guān)系的一種特殊方法。
遞推關(guān)系可以重寫為形式
   hn－a1hn-1－a2hn-2－…－akhn-k＝0  (n≥k)      　(4)
一旦所謂的初始值即H0,h1,h2,…,hn,…能夠給出，則滿足遞推關(guān)系(或更一般地，滿足（2）的數(shù)列) h0,h1,h2,…,hn,…就被唯一的確定。遞推關(guān)系(74)從n=k開始“解開”。忽略初始值并在沒有給出初始值，通過考慮那些形成幾何序列的解并通過適當(dāng)?shù)男薷乃鼈儊碚业健白銐颉钡慕?br /> 線性齊次遞推關(guān)系的求解，可按照離散函數(shù)所采用的與指數(shù)函數(shù)的作用類似的方法進(jìn)行，其中，只對(duì)非負(fù)整數(shù)n(有幾何序列)有定義.
   定理： 令q為一非零數(shù)。則Hn 是常系數(shù)線性齊次遞推關(guān)系
   Hn－a1hn-1－a2hn-2－…－akhn-k＝0  (ak≠0，n≥k)    （5）
的解，當(dāng)且僅當(dāng)qn是多項(xiàng)式方程
   Xk－a1xk-1－a2xk-2―...―ak=0                            (6)
的一個(gè)根。如果多項(xiàng)式方程有k個(gè)不同的根q1,q2,.....,qk, 則
   Hn=c1qn1+c2q2n+ ....... +ckqnk                            (7)
是下述意義下式(5)的一般解：無論給定h0,h1,....,hk-1什么初始值，都存在常數(shù)c1,c2,.....ck，使得公式(7)是滿足遞推關(guān)系(5)和初始條件的唯一的序列。
多項(xiàng)式方程(6)叫做遞推關(guān)系(5)的特征方程，而它的k個(gè)根叫做特征根。根據(jù)定理，如果特征根互異，那么式(7)就是式(5)的一般解。
例    求解滿足初始值H0=1,h1=2和h2=0,和的遞推關(guān)系
          Hn= 2hn-1+hn-2－2hn-3             (n≥3)