定义：建立序列中第n项与其前趋元素间的关系递归算法的分析。
递推关系an
a₁=5 初始条件
a_n= a_n-1 +3 n≥2
a₂=a₁+3=5+3=8
a₃=a₂+3 = 8+3=11
递推关系是由数列第n项前的若干项确定第n项,并由此确定数列。

1、定义

数列a₀,a₁, ...的递推关系是一个由a₀,a₁,… a_n-1中的一些或全部确定a_n的等式。
数列a₀.,a₁, ...的初始条件是对数列的有限个元素给定的确定值。

Fibonacci级数

递推关系f_n=f_n-1+f_n-2 （n≥3） 且 初始条件f₁=1 f₂=2

通项公式

递推关系、递归算法、数学归纳法 三者间关系非常密切！
例：S_n不含111的n位二进制字符串的个数，确定递推关系。
解：
以0开始的
以10开始的
以110开始的
S_n= S_n-1+S_n-2 n≥4
S₁=2,S₂=4，S₃=7 C_k-1*C_n-k

Catalan数

思路：(0,0) → （k，k）→（n，n）通项公式如下：

Hanoi塔

C_n 移动次数
C_n=2C_n-1+1 n≥2
C₁=1 其通项公式为：

习题：P219,1,4,5,37

5.2 求解递推关系

方法：数列a₀,a₁…a_n:的通项公式a_n.
代入法
定常系数线性齐次递推关系
例₁：S_n=2S_n-1 S₀=1。
例₂：a₁=2，a_n=a_n-1+3 n≥2

常系数线性齐次递推关系
形如a_n=c₁a_n-1+c₂a_n-2+ ... +c_ka_n-k c_k≠0的递推关系称为常系数线性齐次递推关系
K阶常系数线性齐次递推关系

• +k个初始条件
• a₀=c₀，a₁=c₁,.. .,a_k-1=G_k-1
• 可以唯一确定一个数列
  例：S_n=2S_n-1 一阶
  f_n=f_n-1+f_n-2

---

定理

设a_n= c₁a_n-1 +c₂a_n-2是2阶常系数线性齐次递推关系，如果S，T是解，则U=bS+dT也是解
如果r是t²- c₁*t -c₂=0的根，则rⁿ是解。
a₀=c₀，a₁=c₁
r₁，r₂是t²-c₁ *t -c₂=0的不同的根，则存在b，d使得

---

例：鹿群n=0:200n=1 : 220
从n-1到n的增长头数为n-2到n-1的增长头数的两倍，写出递推关系，求通项公式。
定理5.2.14
r₁= r₂
设a_n= c₁a_n-1 + C₂a_n-2是2阶常系数线性齐次递推关系
a₀=c₀,a₁=c₁
r₁=r₂=r是t²-c₁ t-c₂=0的(同)根，则存在b，d使得

例：d_n=4（d_n-1-d_n-2） d₀=d₁=1
t²-4t+4=0 r₁=r₂=2
d_n=b2ⁿ+d* n2ⁿ 且d₀=d₁=1
d₀=1=b2⁰+ d * 0 * 2ⁿ =b
d₁=1=b * 2¹+d * 1 * 2¹=2b+2*d=1
b=1,d=-1/2
dⁿ=2ⁿ-n * 2^n-1
习题：P231,1,4,14,22

---

k阶常系数线性齐次递推关系
如果r是方程t^k-c₁ t^k-1-c₂t^k-2-…=0的m重根，
则可证明rⁿ,nrⁿ,…,n^m-1rⁿ都是解

5.3 递推关系与算法分析

用递推关系分析算法运行的时间
基本思想：
a_n表输入量为n时算法运行的时间
确定数列a₀，a₁，…的地推关系和初始条件，通过求解递推关系，确定算法所需要的时间。
例如计算快速排序，归并排序,选择排序等。详见数据结构。