06 第六章 递推关系.pptx

第1页：封面

第六章递推关系

第2页：递推关系导读内容导览

主要内容§6.1递推关系的建立§6.2常系数线性齐次递推关系的求解§6.3常系数线性非齐次递推关系的求解§6.4用生成函数求解递推关系§6.5用迭代和归纳法求解递推关系

第3页：递推关系的建立

• §6.1递推关系的建立
• 错排数Dn的递推关系

第4页：Stirling数的递推关系

Stirling数的递推关系:S2（n+1,k)=S2(n,k-1)+k*S2(n,k)第三章性质3.5.1

第5页：定义6.1 给定一个数列H(0)

定义6.1给定一个数列H(0), H(1),…, H(n),…若存在整数n0，使当n≥n0时，可以用等号（或大于号，小于号）将H(n)与其前面的某些项H(i)，0≤ i ≤n，联系起来的式子叫做一个递推关系。

递推关系(用等号)也称递归关系，递归方程。

第6页：从本质上讲

从本质上讲，递推关系是研究整变量函数的或者说是研究数列的，与此对应的是连续论域中的微分方程。

因此，我们可以类似的方法对它们进行研究。

第7页：f(n)代表了某个组合计数问题

f(n)代表了某个组合计数问题的解，因此递推关系是组合计数的重要工具求出序列的通项表示式f(n)求不出f(n)的显式，可以计算出f(n)的值或者范围

第8页：递推关系的建立内容导览

递推关系的常用求解方法（1）特征根法；

(§6.2,§6.3)（2）迭代法和归纳法；

(§6.5)（3）生成函数法；

（§6.4）

第9页：例6.1.2 Fibonacci数列问题

例6.1.2Fibonacci数列问题是一个古老的数学问题，是于1202年提出的。

问题表述如下:把一对兔子（雌、雄各一只）在某年的开始放到围栏中，每个月这对兔子都生出一对新兔，其中雌、雄各一只。

由第二个月开始，每对新兔每个月也生出一对新兔，也是雌、雄各一只。

问n个月后围栏中有多少对兔子？

这是一个数学模型的形象表示，不能真正用来表示兔子的繁殖规律。

第10页：棋盘覆盖问题

棋盘覆盖问题，用多米诺骨牌（可以看成一个2×1大小的方格）完全覆盖一个2×n的棋盘。

覆盖的方案数等于Fibonacci数f(n).另外一个例子，也体现出递推关系的思想：例6.1.1有n级台阶，某人从下向上走，若每次只能跨1级或者2级，问他从地面走到第n级有多少种不同的方法?甚至是更具体的问题，例如n=10.

第11页：例6.1.3 （Hanoi塔问题）现有A

例6.1.3（Hanoi塔问题）现有A，B，C三根立柱以及n个大小不等的中空圆盘，这些圆盘自小到大套在A柱上形成塔形，如图6.1.1所示，要把n个圆盘从A柱上搬到C柱上，并保持原来的顺序不变，要求每次只能从一根立柱上拿下一个圆盘放在另一根立柱上，且不允许大盘压在小盘上，问至少要搬多少次？

第12页：

本页源文件未提取到正文文字，仅有图片。该页位于「例6.1.3 （Hanoi塔问题）现有A」与「解：记f(n)为n个圆盘从A」之间，建议对照原课件图片补充本页要点说明。

第13页：解：记f(n)为n个圆盘从A

解：记f(n)为n个圆盘从A柱搬到C柱所需的最小次数.整个搬运过程可分成三个阶段；

（1）将套在A柱上面的n-1个圆盘从A柱按要求搬到B柱，搬动次数为f(n-1);（2）把A柱上最下面的那个圆盘搬到C柱上，搬动次数为1;（3）把B柱上的n-1个圆盘按要求搬到C柱上，搬动次数为f(n-1);由加法原则知，f(n)=2f(n-1)+1又显然f(1)=1，所以有如下带有初值的递推关系:f(n)=2f(n-1)+1f(1)=1

第14页：则称作k阶常系数线性齐次递推

则称作k阶常系数线性齐次递推关系(6.2.1)定义6.2.1设k是给定的正整数，若数列的相邻k+1项间满足关系:如果满足下面三个条件都是常数

第15页：(6.2.2)

• (6.2.2)
• 如果有一个数列代入递推关系（6.2.1），使得其对任何n≥k都成立，则称这个数列是递推关系（6.2.1）的解。
• 常系数线性齐次递推关系的一般形式为

第16页：定义6.2.2 方程(6.2.2)叫

定义6.2.2方程(6.2.2)叫做递推关系(6.2.2)的特征方程，它的k个根q1，q2……qk叫做该递推关系的特征根。

其中qi(i=1,2,…,k)是复数。

§6.2常系数线性齐次递推关系的求解特征根法

第17页：(一)无重特征根引理6.2.1设

(一)无重特征根引理6.2.1设q是一个非零复数，则f(n)＝qn是递推关系(6.2.2)的一个解当且仅当q是它的一个特征根。

引理6.2.2设h1(n)和h2(n)是递推关系(6.2.2)的两个解，b1和b2是任意常数，则b1h1(n)＋b2h2(n)也是递推关系(6.2.2)的解。

第18页：定义6.2.3 如果对于递推关系

定义6.2.3如果对于递推关系(6.2.2)的每个解h(n)都可以选择一组常数c1’，c2’，c3’，……ck’,使得h(n)＝c1’q1n＋c2’q2n＋……＋ck’qkn成立，则称b1q1n＋b2q2n＋……＋bkqkn是递推关系通解，其中b1b2……bk为任意常数。

第19页：定理6.2.1 设q1，q

定理6.2.1设q1，q2，……qk是递推关系(6.2.2)的k个不相等的特征根，则f(n)＝b1q1n＋b2q2n＋……＋bkqkn是递推关系(6.2.2)的通解.

第20页：例6.2.1 解关于Fibonacci数

例6.2.1求解关于Fibonacci数的递推关系

第21页：

本页源文件未提取到正文文字，仅有图片。该页位于「例6.2.1 解关于Fibonacci数」与「下一页」之间，建议对照原课件图片补充本页要点说明。

第22页：

本页源文件未提取到正文文字，仅有图片。该页位于「」与「下一页」之间，建议对照原课件图片补充本页要点说明。

第23页：

本页源文件未提取到正文文字，仅有图片。该页位于「」与「例6.2.2 解递推关系」之间，建议对照原课件图片补充本页要点说明。

第24页：例6.2.2 解递推关系

例6.2.2求解递推关系

第25页：

本页源文件未提取到正文文字，仅有图片。该页位于「例6.2.2 解递推关系」与「下一页」之间，建议对照原课件图片补充本页要点说明。

第26页：

本页源文件未提取到正文文字，仅有图片。该页位于「」与「(二)有重特征根定理6.2.2设」之间，建议对照原课件图片补充本页要点说明。

第27页：(二)有重特征根定理6.2.2设

(二)有重特征根定理6.2.2设q1，q2，……qt是递推关系(6.2.2)的不相等的特征根，ei是qi的重数,则递推关系(6.2.2)的通解f(n)=f1(n)+f2(n)+……+ft(n)其中

第28页：例6.2.4 解递推关系

例6.2.4求解递推关系

第29页：例6.2.4 解递推关系（续）

例6.2.4 解递推关系（续）：对

第30页：对通解为解方程组

对通解为解方程组，得c1=5,c2=2,c3=-4所以原递推关系的解为f（n)=5*2n+2n*2n-4*3n

第31页：补例求解递推关系

补例求解递推关系

第32页：(一)一般形式§6.3常系数

• (一)一般形式§6.3常系数线性非齐次递推关系的求解(6.3.1)(6.3.2)
• 对应的齐次递推关系为

第33页：定理6.3.1 k阶常系数线性非齐次递推

定理6.3.1k阶常系数线性非齐次递推关系（6.3.1）的通解是递推关系（6.3.1）的特解加上其相应的齐次递推关系（6.3.2）的通解。

第34页：对于一般g(n)没有普遍的解法

对于一般g(n)没有普遍的解法，只对一些简单的情况可以用待定系数法求f*(n)。

第35页：例6.3.1 解递推关系

例6.3.1求解递推关系

第36页：比较等式两边解

比较等式两边解：因为4不是特征方程的根，所以该递推关系的非齐次特解为，将其代入递推关系，得的系数，得从而a=2.

第37页：而相应齐次递推关系的通解为由定理

而相应齐次递推关系的通解为由定理6.3.1知，非齐次递推关系的通解为由初值得从而故

第38页：例6.3.2 求解递推关系解由于3是特征

例6.3.2求解递推关系解由于3是特征方程的根，所以该递推关系的特解为将它代入递推关系，得到a=6

第39页：从而非齐次递推关系的通解为再

从而非齐次递推关系的通解为再由初值求得于是

第40页：根据前面的分析

根据前面的分析，可知该递推关系的通解为解相应的特征方程为x=2，故齐次解为2n。

设非齐次特解为b，代入原递推关系，得例6.3.3求Hanoi塔问题满足的递推关系所以特解为代入初值得所以

第41页：课后作业题

作业P159: 6.2(3)(4);P159:6.3(3)(4);P159:6.5；

P160: 6.6;P160: 6.7；