1、第六章 递推关系递推 关系是一种重要的组合计数方法 建立递推关系 分析已 有递推关系的性质 求解递推关系主要内容6.1 递推关系的建立6.2 常系数线性齐次递推关系的求解6.3 常系数线性非齐次递推关系的求解6.4* 用生成函数求解递推关系6.5* 用迭代归纳法求解递推关系及其应用 递推关系的定义 递推关系的实例 常系数线性齐次递推关系及其求解 常系数线性非齐次递推关系及其求解（ 1）等差数列（算术数列）h0, h0+q, h0+2q, , h 0+nq,递推关系： hn= hn-1+q一般项： hn= h0+nq前 n+1项和： sn= (n+1)h0+q(n)(n+1)/2（ 2）等比数列
2、（几何数列）h0, qh0, q2h0, , q nh0,递推关系： hn= qhn-1一般项： hn= qnh0前 n+1项和： sn= h0(1-qn+1)/(1-q) 定义 6.1.1 给定一个数的序列 H(0),H(1), H(n), 若存在正整数 n0，使得当 nn0时，可以用等号 (或小于，大于号 )把 H(n)和前面某些项 H(i)， 0 i n，联系起来，这样的式子叫做 递推关系。递推关系也称递归关系，递归方程。从本质上讲，递推关系是研究 整变量 函数的或者说是研究 数列 的，与此对应的是连续论域中的 微分方程 。因此，我们可以类似的方法对它们进行研究。 利用 递推关系和初值
3、在某些情况下可以求出序列的通项表示式 H(n) 。但是对于大多数递推关系，目前还解不出 H(n)的显式来， 即使这样，对于给定的 n也可以从初值开始，一步一步地计算出H(n)的值或者范围，而 H(n)一般代表了某个组合计数问题的解，因此递推关系是 组合计数 的重要工具，同时也是 算法分析 的重要手段。求解递推关系的常用方法（ 1）迭代归纳法；（ 2）特征根法；（ 3）生成函数法； 例 6.1.1（爬楼梯问题）一个小孩要爬上 n阶楼梯，每次可上一阶或两阶，问上 n阶有多少种上法？ 解：显然登上 1阶台阶有 1种方法，登上 2台阶有 2种方法，f(1） =1， f(2)=2 ,称为递推关系的初始条
4、件。设有 f(n) 种方法，要登上这 n阶台阶，最后迈上一个台阶或两个台阶完成 .（ 1）若最后是迈上一个台阶完成的，则前面登上了 n-1阶台阶，有 f(n-1) 种方法；（ 2）若最后是迈上两个台阶完成的，则前面登上了 n-2阶台阶，有 f(n-2) 种方法，根据加法原理有递推关系： f(n)=f(n-1)+f(n-2) .例 6.1.2 Fibonacci数列问题是一个古老的数学问题，是于 1202年提出的，问题表述如下 :把一对兔子（雌、雄各一只）在某年的开始放到围栏中，每个月这对兔子都生出一对新兔，其中雌、雄各一只。由第二个月开始，每对新兔每个月也生出一对新兔，也是雌、雄各一只。问一年后围栏中有多少对兔子？ 这是一个数学模型的形象表示，不能真正用来表示兔子的繁殖规律。
