软件2012组合数学—第六章递推关系.ppt

这说明n3n也是递推关系的解，而且与线性3n无关，所以原递推关系的通解为 代入初值，得： 设递推关系 的特征方程为 令 如果q是P(x)=0的二重根，这q也是Pn(x)=0的二重根，也是P’n(x)=0的根， P’n(x)是Pn(x)的微商，即 因此，q也是xP’n（x）=0的根，而 代入x=q ，得 这说明nqn是原递推关系的解。 可以证明以下的结论：如果q是P(x)=0的e重根,则qn,nqn,n2qn,…,ne-1qn都是原递推关系的解. 定理6.2.2 设q1，q2，……qt是递推关系 f(n)=a1f(n-1)+a2f(n-2)+……+akf(n-k) (n≥k，ak≠0), 的不相等的特征根，其重数分别为e1，e2，……et( e1+e2+……+et=k), 则这个递推关系的通解是： f(n)= f1(n)+ f2(n)+ …… + ft(n) 其中： fi(n)＝c1qi n＋c2nqi n＋……＋ 例6.2.5. 求解递推关系 对 对 通解为 解方程组，得c1=5,c2=2,c3=-4 所以原递推关系的解为 f（n)=5*2n+2n*2n-4*3n 一般形式 ： f(n)=c1f(n-1)+c2f(n-2)+……+ckf(n-k)+g(n) (n≥k,ck≠0,g(n)≠0), 其通解是齐次通解与特解之和， 即f(n)=f′(n)+f″(n) 其中f′(n)是原递推关系的特解； f″(n)是所对应的齐次递推关系 f(n)=c1f (n-1)+c2f (n-2)+……+ckf (n-k)的 通解 。下面主要介绍f′(n)的求解方法。 §6.3常系数线性非齐次递推关系的求解 对于一般g(n)没有普遍的解法，只对一些简单的情况可以用待定系数法求f′(n) 。 一般方法总结: 求齐次关系的一般解 求非齐次关系的一个特解 将一般解和特解结合,通过初始条件确定一般解中出现的常系数值. 比较等式两边 例6.3.1 求解递推关系 解： 因为4不是特征方程的根，所以该递推关系的非齐次特解为 ，将其代入递推关系，得 的系数，得 从而 a=2. 而相应齐次递推关系的通解为 ，由定理6.3.1知，非齐次递推关系的通解为 由初值 得 从而 故 例6.3.2 求解递推关系 解 由于3是特征方程的根，所以该递推关系的特解为 将它代入递推关系，得到 a=6 从而非齐次递推关系的通解为 再由初值 求得 于是 根据前面的分析，可知该递推关系的通解为 解 相应的特征方程为x=2，故齐次解为2n。 设非齐次特解为b，代入原递推关系，得 例6.3.3 求Hanoi塔问题满足的递推关系 所以特解为 代入初值 得 所以 第六章 递推关系 ------一种重要的组合计数方法 基本问题：建立关系；分析性质；求解 主要内容 §6.1 递推关系的建立 §6.2 常系数线性齐次递推关系的求解 §6.3 常系数线性非齐次递推关系的求解 §6.4* 用生成函数求解递推关系 §6.5* 用迭代归纳法求解递推关系及其应用 （1）等差数列（算术数列） h0, h0+q, h0+2q, …, h0+nq,… 递推关系：hn= hn-1+q 一般项： hn= h0+nq 前n+1项和：sn= (n+1)h0+q(n)(n+1)/2 （2）等比数列（几何数列） h0, qh0, q2h0, …, qnh0,… 递推关系：hn= qhn-1 一般项： hn= qnh0 前n+1项和：sn= h0(1-qn+1)/(1-q) 定义6.1.1 给定一个数的序列H(0),H(1),…, H(n),…若存在正整数n0，使得当n≥n0时，可以用等号(或小于，大于号)把H(n)和前面某些项H(i)，0≤ i n，联系起来，这样的式子叫做递推关系。 递推关系也称递归关系，递归方程。从本质上讲，递推关系是研究整变量函数的或者说是研究数列的，与此对应的是连续论域中的微分方程。因此，我们可以类似的方法对它们进行研究。 利用递推关系和初值在某些情况下可以求出序列的通项表示式H(n) 。 但是对