遞推關系的解法研究

全文字數:3283

遞推關系的解法研究

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

對于任意選擇的常數和，上式也是遞推關系的解

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