第六章递推关系;主要内容
§6.1递推关系建立
§6.2常系数线性齐次递推关系求解
§6.3常系数线性非齐次递推关系求解
§6.4用生成函数求解递推关系
§6.5用迭代和归纳法求解递推关系;§6.1递推关系建立;Stirling数递推关系:
S2（n+1,k)=S2(n,k-1)+k*S2(n,k)
第三章性质3.5.1
;定义6.1给定一个数列
H(0),H(1),…,H(n),…
若存在整数n0，使当n≥n0时，能够用等号（或大于号，小于号）将H(n)与其前面一些项H(i)，0≤i≤n，联络起来式子叫做一个递推关系。
递推关系(用等号)也称递归关系，递归方程。;从本质上讲，递推关系是研究整变量函数或者说是研究数列，与此对应是连续论域中微分方程。所以，我们能够类似方法对它们进行研究。;f(n)代表了某个组累计数问题解，所以递推关系是组累计数主要工具;递推关系惯用求解方法
（1）特征根法；(§6.2,§6.3)
（2）迭代法和归纳法；(§6.5)
（3）生成函数法；（§6.4）;例6.1.2Fibonacci数列问题
是一个古老数学问题，是于1202年提出。
问题表述以下:
把一对兔子（雌、雄各一只）在某年
开始放到围栏中，每个月这对兔子都生出一
对新兔，其中雌、雄各一只。由第二个月开
始，每对新兔每个月也生出一对新兔，也是
雌、雄各一只。问n个月后围栏中有多少对兔
子？这是一个数学模型形象表示，不能真
正用来表示兔子繁殖规律。;棋盘覆盖问题，用多米诺骨牌（能够看成一个2×1大小方格）完全覆盖一个2×n棋盘。覆盖方案数等于Fibonacci数f(n).;例6.1.3（Hanoi塔问题）现有A，B，C三根立柱以及n个大小不等中空圆盘，这些圆盘自小到大套在A柱上形成塔形，如图6.1.1所表示，要把n个圆盘从A柱上搬到C柱上，并保持原来次序不变，要求每次只能从一根立柱上拿下一个圆盘放在另一根立柱上，且不允许大盘压在小盘上，问最少要搬多少次？;;;则称作k阶常系数线性齐次递推关系;(6.2.2);定义6.2.2方程
(6.2.2)
叫做递推关系(6.2.2)特征方程，它k个根q1，q2……qk叫做该递推关系特征根。
其中qi(i=1,2,…,k)是复数。;(一)无重特征根;定义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为任意常数。;定理6.2.1
设q1，q2，……qk是递推关系(6.2.2)k个不相等特征根，则
f(n)＝b1q1n＋b2q2n＋……＋bkqkn
是递推关系(6.2.2)通解.;例6.2.1求解关于Fibonacci数递推关系;;;;例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)
其中;例6.2.4求解递推关系;对;对;补例求解递推关系;(一)普通形式;定理6.3.1k阶常系数线性非齐次递推关系（6.3.1）通解是递推关系（6.3.1）特解加上其对应齐次递推关系（6.3.2）通解。;对于普通g(n)没有普遍解法，只对一些简单情况能够用待定系数法求f*(n)。
;;比较等式两边;而对应齐次递推关系通解为;例6.3.2求解递推关系;从而非齐次递推关系通解为;依据前面分析，可知该递推关系通解为
;作业
P159:6.2(3)(4);
P159:6.3(3)(4);
P159:6.5；
P160:6.6;
P160:6.7；