组合数学讲义
第三章 递推关系 §3.1 基本概念
（一） 递推关系
定义3.1.1 （隐式）对数列 aii 0 和任意自然数n，一
个关系到an和某些个ai i n 的方程式，称为递推关系，记作
F a0,a1, ,an 0 (3.1.1)
22222
例 an an 1 an 2 a0 n 0
an 3an 1 2an 2 2a1 1 0
定义3.1.1＇（显式） 对数列 aii 0 ，把an与其之前若干项联系起来的等式对所有n≥k均成立（k为某个给定的自然数），称该等式为 ai 的递推关系，记为
an F an 1,an 2, ,an k (3.1.1)＇
例 an 3an 1 2an 2 2a1 1 （二） 分类
（1） 按常量部分：
① 齐次递推关系：指常量＝0，如
Fn Fn 1 Fn 2；
② 非齐次递推关系，即常量≠0，如hn 2hn 1 1。 （2） 按ai的运算关系：