2012年同等学力计算机综合组合数学辅导3-递推关系.pdfVIP

2012 年同等学力计算机综合组合数学辅导-递推关系 第三章 递推关系 §3.1 基本概念 （一）递推关系 a 定义3.1.1 （隐式）对数列 和任意自然数n，一个关系到 和某些 a i 0 i n 个  的方程式，称为递推关系，记作 a i n i   (3.1.1) F a , a , , a 0 0 1 n 例 a2 a2 a2 a2 n2 0 n n1 n2 0 a 3a 2a 2a 1 0 n n1 n2 1 a 定义3.1.1 ＇（显式）对数列 ，把 与其之前若干项联系起来的等 a i 0 i n   a 式对所有n≥k 均成立（k 为某个给定的自然数），称该等式为 的递推关系， i 记为   (3.1.1) ＇ an F an1,an2 , ,ank 例 a 3a 2a 2a 1 n n1 n2 1 （二）分类 （1） 按常量部分： ①齐次递推关系：指常量＝0，如Fn Fn1 Fn2 ； ② 非齐次递推关系，即常量≠0，如hn 2hn1 1 。 a （2 ） 按 的运算关系： i ① 线性关系，F 是关于 的线性函数，如（1）中的 与 均是如此； a F h i n n ② 非线性关系，F 是 的非线性函数，如 。