算法-求解递归方程的方法

1、 第二章 常用的数学工具2.2 用生成函数求解递归方程2.2.1 生成函数及其性质一、生成函数的定义定义2.1 令是一个实数序列，构造如下的函数：（2.2.1）则函数称为序列的生成函数。例：函数则函数便是序列的生成函数。二、生成函数的性质1. 加法 设是序列的生成函数，是序列的生成函数，则（2.2.2）是序列的生成函数。2移位 设是序列的生成函数，则（2.2.3）是序列的生成函数。3乘法 设是序列的生成函数，是序列的生成函数，则 （2.2.4）是序列的生成函数，其中，4. z变换 设是序列的生成函数，则（2.2.5）是序列的生成函数。特别地，有：（2.2.6）所以，是序列的生成函数。当时，有：

2、（2.2.7）则是序列1,1,1,的生成函数。利用：（2.2.8）可以去掉级数中的奇数项；同样，利用（2.2.9）可以去掉级数中的偶数项。5微分和积分 设是序列的生成函数，对求导数（2.2.10）显然，是序列的生成函数。同样，对求积分（2.2.11）则积分是的生成函数。如果对（2.2.7）式求导数，可得：（2.2.12）则是算术级数1,2,3的生成函数。如果对（2.2.7）式求积分，可得：（2.2.13）则是调和数的生成函数。2.2.2 用生成函数求解递归方程例2.1 汉诺塔（Hanoi）问题。宝石针的编号为、，针串着64片金盘。希望把它们移到针或针。有可是金盘的数量，是移动个金盘的移动次数1

3、 当时， =1。2 当时， 。3 当时， 。递归关系式：（2.2.14）用作为系数，构造一个生成函数：令由（2.2.14）及（2.2.7）式得：所以，令：有：求得。所以： ，它是式中第项的系数。当时，移动次数为。例2.2 菲波那契序列问题。、表示第个月小兔子、大兔子的数目，及第个月兔子的总数目。则：（2.2.15）（2.2.16）（2.2.17）第一式：第个月大兔子的数量，为前一个月大兔子的数量加上前一个月小兔子的数量；第二式：第个月小兔子的数量，为前一个月大兔子的数量；第三式：表示第个月兔子的总量为该月大兔子的数量及小兔子的数量之和。递归方程：（2.2.18）用作为系数，构造生成函数：令：所

4、以，有：有：解得：把、代入，得到：令，则有：所以，第项系数为：2.3 用特征方程求解递归方程2.3.1 k阶常系数线性齐次递归方程一、k阶常系数线性齐次递归方程1、递归方程的形式：（2.3.1）2、递归方程的特征方程取代：两边分别除以，可得：把上式写成：（2.3.2）则式（2.3.2）称为递归方程（2.3.1）的特征方程。二、k阶常系数线性齐次递归方程的求解1、是特征方程的个互不相同的根。则递归方程（2.3.1）的通解为：（2.3.3）2、特征方程的个根中有个重根，递归方程（2.3.1）的通解形式为：（2.3.4）在（2.3.3）及（2.3.4）中，为待定系数。3、求解过程：把递归方程的初始条

5、件代入（2.3.3）或（2.3.4）中，建立联立方程，确定系数，从而可求出通解。例2.3 三阶常系数线性齐次递归方程如下：解 特征方程为：把方程改写成：对特征方程进行因式分解，得：则有特征根：所以，递归方程的通解为：由初始条件得：解此联立方程，得：则递归方程的解为：例2.4 三阶常系数线性齐次递归方程如下：解 特征方程为：把特征方程改写成：进行因式分解：最后得：求得特征方程的根为：所以，递归方程的通解为：代入初始条件：解此联立方程，得：则递归方程的解为：2.3.2 k阶常系数线性非齐次递归方程一、k阶常系数线性非齐次递归方程1、递归方程的形式：（2.3.5）2、通解形式：其中，是对应齐次递归方

6、程的通解，是原非齐次递归方程的特解。3、特解的求取1）是的次多项式，即（2.3.6）其中，是常数。特解也是的次多项式：（2.3.7）其中，为待定系数。2）是如下形式的指数函数：（2.3.8）其中，、为常数。a) 不是特征方程的重根，特解为：（2.3.9）其中，为待定系数。b) 是特征方程的重特征根，特解的形式为：（2.3.10）其中，是待定系数。例2.5 二阶常系数线性非齐次递归方程如下：解 对应的齐次递归方程的特征方程为：把此方程转换为：得到特征根为：所以，对应的齐次递归方程的通解为：令非齐次递归方程的特解为：代入原递归方程，得：化简后得到：由此，得到联立方程：解此联立方程，可得：所以，非齐

7、次递归方程的通解为：把初始条件代入，有：解此联立方程，得：最后，非齐次递归方程的通解为：例2.6 二阶常系数线性非齐次递归方程如下：解 对应齐次递归方程的特征方程为：此方程可改写成：所以，方程的解为：齐次递归方程的通解为：令非齐次递归方程的特解为：把特解代入原非齐次递归方程，得：整理得：可得联立方程：解此联立方程得：所以，非齐次递归方程的通解为：用初始条件代入：解此联立方程得：最后，非齐次递归方程的解为：解方程步骤归纳（1）求齐次方程的解 但系数项待定（2）确定特解 将特解带入原方程，确定各系数（3）确定通解，由给定的初值确定确定齐次方程的未定系数。 2.4 用递推方法求解递归方程2.4.1

8、递推非齐次递归方程：（2.4.1）其中，、是常数，是的某一个函数。直接把公式应用于式中的，得到： （2.4.2）例2.7 汉诺塔问题。由（2.2.14），汉诺塔的递归方程为：直接利用（2.4.2）式于汉诺塔的递归方程。此时，从递推到1，有：2.4.2 用递推法求解变系数递归方程一、变系数齐次递归方程：（2.4.3）利用递推方法，容易得到：（2.4.4）例2.8 解如下递归函数：由（2.4.4）式，容易得到：二、变系数非齐次递归方程：（2.4.5）其中，是常数，和是的函数。利用（2.4.5）式对进行递推，有： （2.4.6）例2.9 解如下的递归函数：对方程进行递推，有： 如果直接使用公式（2.4.6），此时，有：得到同样结果。例2.10 解如下的递归方程解 对方程进行递推，有：由公式（2.1.24），得如果直接使用公式（2.4.6），此时，同样有：2.4.3 换名例2.11 解如下的递归方程：其中， 。解 把表示成的关系，原递归方程改写为：再令：于是，原递归方程可写为：对上面方程进行递推，有：如果直接使用（2.4.6）式，可得：结果一样。例2.12 解如下的递归方程：其中，、为常数，。解 把表示成的关系，原递归方程改写为：再令：于是，原递归方程可写为：直接使用