1、主要内容l 递推方程的定义及实例l 递推方程的公式解法l 递推方程的其他解法l 生成函数及其应用l 指数生成函数及其应用l Catalan数与 Stirling数第十三章 递推方程与生成函数113.1递推方程的定义及实例定义 13.1 设序列 a0, a1, , an, , 简记为 an . 一个把 an 与某些个 ai (i 0 and Ai key5. do Ai+1 Ai; i i 17. Ai+1 key 4递推方程的实例 :算法分析例 2 哪种排序算法在最坏情况下复杂度比较低？插入排序，归并排序 插入排序 W(n) = W(n 1) + n 1 W(1) = 0解得 W(n) = O
2、(n2). 归并排序，不妨设 n = 2k. W(n) = 2W(n/2) + n 1W(1) = 0解得 W(n) = O(nlogn) 513.2 递推方程的公式解法l 特征方程、特征根l 递推方程的解与特征根的关系l 无重根下通解的结构l 求解实例l 有重根下通解的结构l 求解实例6其中 a1, a2, , ak为 常数， ak 0 称 为 k 阶 常系数 线 性 齐 次 递 推方程b0, b1, , bk1 为 k 个 初 值定义 13.2 常系数线性齐次递推方程的标准形： 常系数线性齐次递推方程实例： Fibonacci 数列的递推方程7特征方程与特征根定 义 13.3 特征方程 x
3、k a1xk1 ak = 0，特征方程的根称 为递 推方程的 特征根实 例： 递 推方程 fn = fn1 + fn2特征方程 x2x1 = 0 特征根8递推方程解与特征根的关系定理 13.1 设 q 是非零复数，则 qn 是递推方程的解当且仅当q 是它的特征根 . qn是递推方程的解 qn a1qn1 a2qn2 akqnk = 0 qnk (qk a1qk1 a2qk2 ak) = 0 qk a1qk1 a2qk2 ak = 0 （因为 q0） q 是它的特征根 定理 13.2 设 h1(n) 和 h2(n) 是递推方程的解， c1,c2为任意常数 ,则 c1h1(n)+c2h2(n) 也
4、是这个递推方程的解 .推论 若 q1, q2, , qk 是递推方程的特征根，则 c1q1n + c2q2n + + ckqkn 是该递推方程的解，其中 c1, c2, , ck 是任意常数 . 9无重根下通解的结构定义 13.4 若对常系数线性齐次递推方程的每个解 h(n) 都存在一组常数 c1,c2, ck 使得h(n) = c1q1n+c2q2n+ ckqkn 成立，则称 c1q1n + c2q2n + + ckqkn 为该递推方程的 通解 定理 13.3 设 q1, q2, , qk 是 常系数线性齐次 递推方程不等的特征根，则 H(n)= c1q1n + c2q2n + + ckqkn为该递推方程的通解 .10
