组合数学讲义 3章 递推关系

组合数学讲义

第三章 递推关系 §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的运算关系：

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说教育文库组合数学讲义 3章 递推关系在线全文阅读。