第七章递推关系和生成函数.pptVIP

第7章 递推关系和生成函数;7.1 一些数列;例2 (Fibonacci问题): Fibonacci数列是递推关系的又一典型问题, 数列的本身有着许多应用. (1) 问题的提出：假定初生的一对雌雄兔子, 从出生的第2个月之后每个月都可以生出另外一对雌雄兔. 如果第1个月只有一对初生的雌雄兔子, 问n个月之后共有多少对兔子？;1月;5月;(2) 求递推关系: 设满n个月时兔子对数为Fn,则第n-1个月留下的兔子数目为Fn-1对;当月新生兔数目为Fn-2对, 即第n-2个月的所有兔子到第n个月都有繁殖能力 ? Fn= Fn-1+ Fn-2, F1 =F2=1 (7.1) 由递推关系(7.1)式可依次得到 F3= F1+F2=2, F4= F2+F3=3, F5= F3+ F4=3+2=5, ? 前几项为：0，1，1，2，3，5，8，13，21，34，55，89，144，233，…;(3) Fibonacci数列的性质 部分和Sn=f0+f1+f2+…+fn=fn+2-1 Fibonacci数列是偶数当且仅当n能被3整除 Fibonacci数列满足公式;;;7.2 线性齐次递推关系;hn=a1hn-1+a2hn-2+…+akhn-k (n≥k) 其中a1,a2,??,ak 是常系数，称为常系数线性齐次递推关系。 定理7.2.1 令q为一非零数。则hn=qn是hn-a1hn-1-a2hn-2-…-akhn-k =0(ak≠0,n≥k) 的解，当且仅当q是多项式方程xk-a1xk-1-a2xk-2-…-ak=0的一个根。如果多项式方程有k个不同的根q1,q2,…,qk，则hn=c1q1n+c2q2n+…+ckqkn;例6：求满足初始值h0=1,h1=2,h2=0的递推关系hn=2hn-1+hn-2-2hn-3 (n≥3)的解 例7：只由三个字母a,b,c组成的长度为n的一些单词将在通信信道上传输，满足条件：传输中不得有两个a连续出现在任一单词中。确定通信信道允许传输的单词个数。 例8：递推关系hn=4hn-1-4hn-2 (n≥2)的解 定理7.2.2 令q1,q2,…,qt为hn=a1hn-1+a2hn-2+…+akhn-k (ak≠0,n≥k) 的特征方程的互异的根。此时，如果qi是si重根，则对qi部分一般解为Hn(i)=(c1+c2n+…+csinsi-1)qin;7.3 非齐次递推关系;图;(1) 算法设计： n=2时, 圆盘1从A套在B上；把圆盘2从A转移到C上；把圆盘1从B上转移到C上. 完毕. n=3时, 把圆盘1从A转移到C上；把圆盘2从A转移到B上；把圆盘1从C上转移到B上; 把圆盘3从A套在C上; 把圆盘1从B再转移到A上; 把圆盘2从B转移到C上, 把圆盘1从A套在C上. 完毕. 看看n=3的演示过程.;A;假定n-1个盘子的转移算法已经确定. 对n个圆盘问题, 先把上面的圆盘1,2,…, n-1转移到B上, 再把最后一个盘子转移到C上, 然后把B上的n-1个圆盘转移到柱C上. 转移完毕. 这运用的是递归算法n=2时给出了算法; n=3时先利用n=2时的算法把圆盘1, 2移B上; 再把圆盘3转移到柱C上;再利用n=2时的算法把B上两个圆盘转移到柱C上. n=4,5,?以此类推. ;(2) 算法分析：令hn表示n个圆盘所需要的转移次数. 根据算法先把前面n-1个盘子转移到B上; 然后把第n个盘子转移到C上; 最后再一次将B上的n-1个盘子转到C上. 算法可实现性可用归纳法得到. 因n=2时对, 假定n-1对, 那么n自然也对. 关于转移次数容易得到一个递归关系: hn=2hn-1+1 , h1=1. ;例10：解hn=3hn-1-4n (n≥1) h0=2 步骤总结 求齐次关系的一般解 求非齐次关系的一个特解 将一般解和特解联合，按初始条件求系数 困难在于特解的求解。 例11： hn=2hn-1+3n (n≥1) h0=2 例12：hn=3hn-1+3n (n≥1) h0=2 例13： hn=hn-1+n3 (n≥1) h0=0;7.4 生成函数（母函数）;但是, 如果一个未知数列没有简单公式, 或者即便存在, 但是很复杂, 很不容易得到, 我们也不知道, 该怎么办? 如果我们还希望研究这个数列, 讨论它的性质, 该如何下手? 举一个极端的例子, 假定这个数列是2, 3, 5, 7, 11, 13, 17, 19, 23, …., 此处an是第n个素数. 这样的情况, 期望任何简单的公式都是不合理的. ;母函数把数列的所有成员用一种非常巧妙的方法联系在一起, 虽然这样做并不一定能得到数列的简单公式, 可是也许能够给出一个幂级数和的简单公式, 展开这个和函数, 所得到的幂级