定理
r 阶线性常系数非齐次递推关系的通解an是该非齐 次递推关系的一个特解an[p]，加上其相应的齐次 递推关系的通解an[c] [ p] [c ] 即
an an
an
哈尔滨工程大学课件 沈晶 制作
多项式型非齐次递推关系
一般形式 a c a ... c a p( n) n 1 n 1 r nr
哈尔滨工程大学课件 沈晶 制作
定义
如果递推关系式1的每个解an[s]都可以选择一组常 数B1’ , B2’ ,…, Br’ 使得
an B 1 m B 2 m ... Br m
' n 1 ' n 2 '
s
n r
' n n n 成立，则称 B1 m1 B'2 m2 ... B'r mr 是递推关系式1的通解，其中：B1’ , B2’ ,…, Br’是 任意常数。
D1
Dn
Dn1
D2
P

D3
哈尔滨工程大学课件 沈晶 制作
r 阶递推关系的一般形式
an c1 nan1 c2 nan 2 ... cr nan r en 其中：n r , cr 0
若e(n) = 0，称其为齐次递推关系式
若e(n)≠0，称其为非齐次递推关系式
哈尔滨工程大学课件 沈晶 制作
常系数齐次线性递推关系
一般形式：
an c1an1 c2an 2 ... cr an r 0 其中：r 0 c
特征方程：
（式1）
m r c1m r 1 c2 m r 2 ... c r 0
哈尔滨工程大学课件 沈晶 制作
哈尔滨工程大学课件 沈晶 制作
指数型非齐次递推关系
一般形式 an c1an ... cr an b n pn 1 r 定理：当b是对应的齐次递推关系的 k 重特征根时 （若b不是特征根，则 k=0） 该非齐次递推关系的一个特解的形式为
[ anp ] b n n k B0 B1n B2 n 2 ... Bl n l
an n n 2 2
例8 10个数字(0~9)和4个运算符(+,-,,) 组成14个 元素，求由其中的n个元素构成的排列组成的算术 表达式的个数（含除数为0的情况） 解： n n 15 65 15 65 an 5 65 5 65 4 65 4 65




哈尔滨工程大学课件 沈晶 制作
哈尔滨工程大学课件 沈晶 制作
递推关系的建立
例5 用an表示包含偶数个0和偶数个1的n位三进制 序列的个数，用bn表示包含偶数个0和奇数个1的n 位三进制序列的个数，用cn表示包含奇数个0和偶 数个1的n位三进制序列的个数。求关于an, bn, cn (n=1,2...)的递推关系。
an an 1 bn 1 cn 1 n 1 解： bn 3 cn 1 n 1 cn 3 bn 1 a 1,b 1,c 1 1 1 1
当ci(n)=ci时（i =1,2,…,r）称为常系数递推关系
哈尔滨工程大学课件 沈晶 制作
第6-7讲 递推关系
递推关系的定义 递推关系的建立 递推关系的求解
常系数线性齐次递推关系求解
非齐次递推关系的求解 非线性递推关系的求解 母函数解递推方程
哈尔滨工程大学课件 沈晶 制作
递推关系的求解
经典解法 母函数解法 迭代法 置换法 归纳法 相加削去法
求解过程
求齐次递推关系的通解 求非齐次递推关系的特解 列出非齐次递推关系的通解形式 根据初始条件确定待定系数
哈尔滨工程大学课件 沈晶 制作
多项式型非齐次递推关系
例10 an=2an-1+1, a1=1 解： n 2n 1 a
例11 an=an-1+2(n-1), a0=2, 求an =? 解： n n 2 n 2 a
哈尔滨工程大学课件 沈晶 制作
递推关系的建立
例6 平面上有一点P，它是n个区域D1, D2, ... Dn的 共同交界点，现取k种颜色对n个区域着色，要求 相邻区域着不同的颜色，试求着色方案。
解：
an ( k 2)an1 ( k 1)an 2 a2 k ( k 1), a3 k ( k 1)( k 2)
哈尔滨工程大学课件 沈晶 制作
课后练习
求n位二进制数最后三位出现010图像的个数。 参考答案：
an 2
n 3
an 2 , a3 1
2 1 1 n an cos n sin n 2 5 2 5 2 10
哈尔滨工程大学课件 沈晶 制作
H i n B0 m B1 n m ... Bei 1 n
B0 B1 n ... Bei 1 n
而递推关系式1的通解为：

n i
n i
e i 1
e i 1
m
min
n i
an H1 (n) H 2 (n) ... H i (n)
哈尔滨工程大学课件 沈晶 制作
无重特征根
定理：设m1,…,mr是递推关系式1的r个互不相等的 特征根，则： ' n ' n ' n
an B 1 m1 B 2 m2 ... Br mr
是递推关系式1的通解。
哈尔滨工程大学课件 沈晶 制作
有重特征根
定理：设m1, m2, …,mi是递推关系式1的全部互不 相等的特征根，其重数分别为e1, e2, …,ei (e1+e2+…+ei = r) 则递推关系式对应mi部分的通解是：
哈尔滨工程大学课件 沈晶 制作
递推关系的建立
例1 有一个小孩要爬上有n个台阶的楼梯，他一步 可以爬一个台阶或者两个台阶。这个小孩爬上这n 个台阶楼梯的不同方法的数目记作an，求an的递 推关系。 解：
a n a n 1 a n 2
a1 1, a2 2
哈尔滨工程大学课件 沈晶 制作
a2,1 a3,1 a4,1 1, 对于 n 0 或n 1 或n 4, 有an,1 0
an,k 6an 2,k 1 10an 3,k 1 15an 4,k 1
a2,1 6, a3,1 10, a4,1 15, 对于 n 0 或n 1 或n 4, 有an,1 0
其中， p( n)是n的l 次多项式
定理：当 l 是相应的齐次递推关系的 k 重特征根 时（若 l 不是该齐次递推关系的根时，k = 0）
a
[ p] n
n B0 B1n B2 n ... Bl n
k 2

l

是该非齐次递推关系的一个特解。
哈尔滨工程大学课件 沈晶 制作
多项式型非齐次递推关系
递推关系的建立
例2 设平面上有n条直线，其中每对直线都相交， 但任意三条直线都不交于一点。这样的n条直线把 平面分成的区域个数记作an，求an的递推关系。 解： a a n
n n 1
a1 2
哈尔滨工程大学课件 沈晶 制作
递推关系的建立
例3 在信道上传输由a,b,c三个字母组成的长为n的 字符串，若字符串中有两个a连续出现，则信道就 不能传输。令an表示信道可以传输的长为n的字符 串的个数，求an满足的递推关系。 解：a 2a 2a n n 1 n 2
引理1
设m是非零实数或复数，则mn是递推关系式
an c1an1 c2an 2 ... cr an r 0 其中：r 0 c
的解的充要条件是：m是上述递推关系式1的特征 方程的特征根。
哈尔滨工程大学课件 沈晶 制作
引理2
如果an[1],an[2]都是递推关系式
an c1an1 c2an 2 ... cr an r 0 其中：r 0 c
a1 3, a2 8
哈尔滨工程大学课件 沈晶 制作
递推关系的建立
例4 把 n 个相同的球放入 k 个不同盒子中，每个 盒子中的球不少于2个又不多于4个。其不同的放 法的数目记作an,k，求an,k的递推关系，如果这n个 球取自3种颜色的球如何？ 解：
a n , k a n 2 , k 1 a n 3 , k 1 a n 4 , k 1
常系数齐次线性递推关系的求解
例9 n阶行列式
2 1 0 0 1 2 1 0 0 1 2 1 . 0 1 2 . . 0 1 . 0 . 0 . 0 . 0 0
d n 2d n1 d n 2
d1 2, d 2 3
dn 1 n
0 1 2n
哈尔滨工程大学课件 沈晶 制作
举例： 汉诺塔问题
an 2an1 1 a 1块盘子问题 块盘子问题 a1 1 a64 18446744073709551615
n-1
哈尔滨工程大学课件 沈晶 制作
第6-7讲 递推关系
递推关系的定义 递推关系的建立 递推关系的求解
常系数线性齐次递推关系求解
非齐次递推关系的求解 非线性递推关系的求解 母函数解递推方程
第6-7讲 递推关系
递推关系的定义 递推关系的建立 递推关系的求解
常系数线性齐次递推关系求解
非齐次递推关系的求解 非线性递推关系的求解 母函数解递推方程
哈尔滨工程大学课件 沈晶 制作
递推关系的定义
定义
对数列{ai | i ≥0}和任意自然数 n，一个关系到an和某些 ai (i <n)的方程，称为递推关系。 初始条件的个数与递推 关系的阶相等 记作 F (a0 , a1 , a2 ,…, an) = 0 初始条件 a0=d0, a1=d1, ..., ak=dk