解：原递推关系的解为
f(n)?2n?2n?1n。
第三节 常系数线性非齐次递推关系的求解
k阶常系数线性非齐次递推关系的一般形式为
fn?c1f(n?1)?c2f(n?2)??ckf(n?k)?g(n)(n?k),(4.3.1)
其中，c1,c2,?,ck为常数，ck?0,g(n)?0。递推关系（4.3.1）对应的齐次递推关系为
f(n)?c1f(n?1)?c2f(n?2)???ckf(n?k),(4.3.2)。
定理 4.3.1 k阶常系数线性非齐次递推关系（4.3.1）的通解是递推关系（4.3.1）的特解加上其相应的齐次递推关系（4.3.2）的通解。
下表对于几种g(n)给出了递推关系（4.3.1）的特解的一般形式。
g(n) 特征多项式f(n) P(?)?0 f?(n) ?n ns 特解a?n的一般形式 ?是P(x)?0的m重根 P(1)?0 1是P(x)?0的m重根 P(?)?0 anm?n bsns?bs?1ns?1???b1s?b0 nm(bsns?bs?1ns?1???b1s?b0) ?nns ?n(bsns?bs?1ns?1???b1s?b0) nm?n(bsns?bs?1ns?1???b1s?b0) ?是P(x)?0的m重根
例1 求解递推关系 ?f(n)?2f(n?1)?4n?1, ??f(0)?1.
例2 求和14?24???n4。
例3 求解递推关系
?f(n)?4f(n?1)?4f(n?2)?n?2n, ??f(0)?0,f(1)?1.
例4 求解Hanoi塔问题满足的递推关系
?f(n)?2f(n?1)?1,。 ??f(0)?0
第四节 用迭代归纳法求解递推关系
迭代归纳法也是求解递推关系的一种方法，尤其对于某些非线性的递推关系，不存在求解的公式，不妨用这种方法来试一试。
例1 求解递推关系 ?f(n)?f(n?1)?n3, ??f(0)?0
迭代法并不仅仅局限于如例子1所示的直接导出的表达式。利用迭代法，还可以先将原递推关系化简，然后再求解。
（1）将非齐次递推关系齐次化
例2 求解递推关系 ?f(n)?2f(n?1)?4n?1, ?(4.4.1)?f(1)?3.
（2）将变系数的一般线性递推关系化为常系数线性递推关系
例3 求解递推关系
n?1?f(n)?f(n?1)?1,? 2n???f(0)?1.
（3）将一阶高次递推关系通过变量代换化为一阶线性递推关系。
应用：估计快速排序算法的平均复杂度
第五节 Fibonacci 数和Catalan数
简述
Fibonacci数列和Catalan数列是递推关系的典型问题，它们经常出现在组合计数问题中，而这两个数列本身的应用也十分广泛。
4.5.1 Fibonacci数
Fibonacci 数的来源—问题
关于Fibonacci数列的问题是一个古老的数学问题，它是由意大利著名学家Fibonacci于1202年提出来的。
问题：把一对雌雄兔子放到围栏中，每个月这对兔子都生出一对新兔子，其中雌雄各一只。从第二个月开始，每对新兔子每个月也生出一对新兔子，也是雌雄各一只。问一年后围栏中由多少对兔子？
根据分析，令f(n)表示第n个月开始围栏中兔子对数，有f(1)?1,f(2)?2，则有
?f(n)?f(n?1)?f(n?2)(n?3),(4.5.1) ??f(1)?1,f(2)?2.这是一个带有初值的递推关系，如果规定f(0)?1， 则递推关系（4.5.1）就变成 ?f(n)?f(n?1)?f(n?2)(n?2), ?(4.5.2)?f(0)?1,f(1)?2.满足递推关系（4.5.2）的数列就叫做Fibonacci数列，它的项就叫做Fibonacci数。
与费波纳奇数列有关的数字现象很多：两个连续的费波纳奇数字没有公约数；数列中任何10个数之和，均可被11整除等。无论是从宏观的宇宙空间到微观的分子原子，从时间到空间，从大自然到人类社会，政治、经济、军事??等等，人们都能找到费波纳奇数的踪迹。在期货股票市场的分析中，费波纳奇数字频频出现。例如在波浪理论中，一段牛市上升行情可以用1个上升浪来表示，也可以用5个低一个层次的小浪来表示，还可继续细分为21个或89个小浪；而一段熊市行情可以用1个下降浪来表示，也可以用3个低一个层次的小浪来表示，还可以继续细分为13个或55个小浪；而一个完整的牛熊市场循环，可以用一上一下2个浪来表示，也可以用8个低一个层次的8浪来表示，还可以继续细分为34个或144个小浪。
Fibonacci数的性质
（1）Fibonacci数f(n)可以表示为二项式系数之和，即
?n??n?1??n?k??n?f(n)????????,k?. ??????2??0??1??k?（2）f(0)?f(1)???f(n)?f(n?2)?1. （3）f(0)?f(2)???f(2n)?f(2n?1). （4）f(1)?f(3)???f(2n?1)?f(2n)?1.
（5）f2(0)?f2(1)???f2(n)?f(n)f(n?1).
（6）f(n?m)?f(m?1)f(n?1)?f(m?1)f(n)(m?2).
自然界中到处可見Fibonacci数列的踪迹。树技上的分枝数，多数花的瓣数都是费氏数：火鹤 1、百合3，梅花5，桔梗常为8，金盏花13，?等等。费氏数列也出现在松果上。一片片的鱗片在整粒松果上顺着两组螺线排列：一组呈顺时针旋转，另一组呈反时针，顺时针螺线的排列数目是8，反时针方向则为13，而另一组常出现的数字是“5 及 8”。向日葵也是一样，常見的螺线数目为“34 及 55”，较大的向日葵的螺线数目则为“89 及 144”，更大的甚至还有“144 及 233”。这些全都是费氏数列中相邻两项的数值。
例1 用多米诺牌（可以看作一个2×1大小的长方块）完全覆盖一个n×2的棋盘，覆盖的方案等于Fibonacci数。
例2 一个小孩上楼梯，每次可上一阶或两阶，问上n阶楼梯有多少种不同的方法？ ?h(n)?h(n?1)?h(n?2)(n?3) ??h(1)?1,h(2)?2.
4.5.2 Catalan数
Catalan数首先是由Euler在精确计算对凸n边形的不同的对角三角形剖分的个数问题时得到的，它经常出现在组合计数问题中。
问题：在一个凸n边形中，通过插入内部不相交的对角线将其分成一些三角形区域，问由多少种不同的分法？
令h(n)表示分一个n?1条边的凸多边形为三角形的方法数，并规定h(1)?1。 利用递推方法，我们得到h(n)的递推关系如下：
h(n)??h(k)h(n?k)
k?1n?1这个递推关系若直接求解，将是非常困难的，但利用后面将学习的生成函数，可以较容易的2求得
1?2n?2?hn???。
n?n?1?我们称hn为Catalans数。
1?6?例如对五边形，有h4????5。五种划分方案如下图。
4?3?
例 证明有n个叶子的完全二叉树的个数为Catalan数h(n)。
例 证明从(0,0)点到(n,n)点的除端点外不接触直线y?x的路径为2h(n),其中h(n)为Catalan数。
本章小结：
Fibonacci数是一个非常神奇且具有众多有趣性质的数列，问世几百年来，一直吸引着各国的研究者，至今方兴未艾。可以说，世界上没有哪一个数学问题的研究