1、第 7章 递推关系与生成函数7.1 递推关系与递推求解7.2 特征方程解法7.3 生成函数解法递推（递归）关系是计数的一个强有力的工具，特别是在做算法分析时是必需的，有大量的递归算法的时间特性体现出递推关系。递推关系的求解的主要方法包括递推、母函数、特征方程等方法。7.1 递推关系与递推求解例 1确定平面一般位置上的 n个互相交叠的圆所形成的区域数。所谓互相交叠是指每两个圆相交在不同的两个点上。解 记个数为 hk。 h0=1， 表示一个平面， h1=2。 第 n个圆与前 n-1个圆有 2(n-1)个交点，被分割成 2(n-1)段弧，每个弧将它所在的区域分成两半。故有递推关系：hn=hn-1+2
2、(n-1)， n2递推关系与求解由于上述关系对一般的 n都成立，有：hn=hn-1+2(n-1)=hn-2+2(n-2)+2(n-1)=hn-3+2(n-3)+2(n-2)+2(n-1)=.=h1+2(1)+2(2)+.+2(n-1)=2+2(1)+2(2)+.+2(n-1)=n2-n+2递推关系与求解例 2求下述方程的解析解。解 此为可进行 “迭代 ”求解的典型方程。递推关系与求解7.2 特征方程解法z1. 线性齐次递推关系定义 1若有 hn的递推关系 :其中的 ak0， 且 ai和 bn可以与 n有关。称为线性递推关系。若 bn为 0，则称为齐次方程。若 ai为常数，则称为常系数方程。特征
3、方程解法定理 1若 q为一 非零数 ，则 hn=qn是常系数线性齐次递推关系的解，当且仅当 q是多项式方程（ 特征方程 ）的一个根。如果多项式方程有 k个不同的根 q1,qk， 则是递推关系的一般解：即对任何给定的初始值h0,h1,hk-1， 都存在常数 c1,c2,ck-1 ，使公式满足递推关系。特征方程解法证明： hn=qn是递推关系的解，当且仅当对所有 nk成立。因 q非 0，可消去 qn-k。 方程等价于即第一个结论成立。特征方程解法由于 qi互异， qin都是递推关系的不同解，故也是递推关系的解。对任意的初始值，有特征方程解法此方程的系数矩阵为范德蒙行列式：可见方程有唯一解，结论成立。特征方程解法
