递推关系的解法研究

全文字数: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)

相关论文