由于无等于1的特征根，所以递推关系
an 5an1 6an2 n 2(n 2)有特解an An B, A, B
是待定系数，代入上式 得A 1 , B 11 ,则
24
an
c1
2n
c2
3n
1 2
n
11 4
,
c1,
c2是待定系数，由初
始条件得
c1
3, c2
1，所以an
3 2n
3n
1 2
3.2 递推关系
递推关系
特征方程没有重根的常 系数线性齐次递推关系
特征方程有重根的常系数 线性齐次递推关系
两类常系数线性非齐次 递推关系
3.2 递推关系
常系数线性齐次递推关系
3.2 递推关系
❖ 研究思路： 先假设方程有解， (1) 找出方程解的结构； (2) 方程有解满足那些条件 (3) 满足这些条件的方程是否有解
an c1 c2n c33n c4n3n , 其中c1, c2 , c3, c4为待定系数
由初始条件得 c1 2, c2 1, c3 3, c4 1,故 an 2 n 3n1 n3n (n 0,1,2,)
特征方程有重根
练习
(1)习题19(1)(3); (2)习题20(1)
即思考问题时，先找到必要条，再证必要条件是不是充 分条件，是的话当然好；ቤተ መጻሕፍቲ ባይዱ是的话，有需加哪些条件？
常系数线性齐次递推关系
3.2 递推关系
常系数线性齐次递推关系
3.2 递推关系
❖ 1、满足递推关系的数列由其前k项决定， 前k项不同，得到的满足递推关系的 数列也就不同。
2、任给k个常数，就可以构造满足递推关系的数列
又因为 a0 133, a1 1211112144 133 23 所以， an能被133 整除
特征方程没有重根
3.2 递推关系
❖ 类似线性空间，如果n维线性空间里，若线性映射A有n 个线性无关的特征向量，则这n个线性无关的特征向量 做成一组基底。
❖ 属于不同特征值的特征向量线性无关， ❖ 当A有n个特征值时，这n个线性无关的特征向量做成一
72
0
8
22
42
8
14
20
6
6
因为f (0) 0, f (0) 0, 2 f (0) 8, 3 f (0) 6,所以
n k(k
k 0
1)(k
2)
n k 0
f
(k)
3 j 0
n j
11j
f
(0)
1 n4 4
5 n3 6
1 n2 4
5 6
n
3.1 差分
3.1 差分
例3.3试求一数列{ f (n)}n0使其前5项依次是1,3,7,13,21, 其通项f (n)是n的多项式且次数最低
解：设数列{ f (n)}n0为所求，则其差分表为
1
3
7
13
21
2
4
6
8
2
2
2
0
0
由定理3.6，k f (0) 0(k 3)
由牛顿公式
f
(n)
En
f
(0)
n i0
n i
i
f
(0)
n2
n
1
练习
（1 练习1(1)）f (n) 2n (1)n ,求k f (n)
n
2(练习4)用差分法求和 (k 1)(k 2)2 k 0
an c1 c2 3n 4 2n , c1, c2是待定系数，由初始条件得 c1 1, c2 5，所以an 1 53n 4 2n (n 0)
常系数线性非齐次递推关系
练习
(1)习题21(1)(3)
3.3Fibonacci数 ❖ 3.3Fibonacci数
f (n)
3.3Fibonacci数
分析：因为 q是特征根 qn是解
5 13 和 5 13 是特征方程的两个特征 根
2
2
所以，特征方程为 x2 5x 3 0
从而un an是递推关系un 5un1 3un2 (n 2)的一个解，故 an 5an1 3an2 (n 2)
特征方程没有重根
3.2 递推关系
分析：要证明 an (n 0)能被133整除，可以从数列满足 的递推关系出发 因为an 121 11n 12 144 n ,可知11,144是特征根 类似上例可知特征方程为x2 155x 1548 0 an满足递推关系an 155un1 1548un2 (n 2)
常系数线性非齐次递推关系
3.2 递推关系
解：递推关系 an 4an1 3an2 2n (n 2)的特征方程为 x2 4x 3 0, 特征根为 x1 1, x2 3,故其通解为 an c1 c2 3n 因为2不是特征根，所以递推关系
an 4an1 3an2 2n (n 2)有特解an A 2n , A是待定系数， 代入上式得A 4,则
3(练习5)试求一数列{ f (n)}n0使其前4项依次是3,7,21,51, 其通项f (n)是n的多项式且次数最低 4(练习6)已知f (n)是n的三次多项式且f (0) 1, f (1) 1,
n
f (2) 3, f (3) 19,确定f (n),并求 f (k) k 0
3.2 递推关系
解递推关系的一般步骤 (1)解特征方程，求出特征根；q是特征根 qn是解 (2)写出通解； (3)由初始条件确定待定系数； (4)得出解
特征方程没有重根
3.2 递推关系
解：所给递推关系的特征方程为x4 8x3 22x2 24x 9 0 的特征根为x1 x2 1, x3 x4 3,所以
n
11(n 4
0)
常系数线性非齐次递推关系
3.2 递推关系
解非齐次递推关系的一般步骤 (1)先解所对应齐次递推关系，：解特征方程，求出特征根， 写出通解； (2)根据非齐次递推关系的形式，找出特解； (3)写出非齐次递推关系的通解：齐次的通解 非齐次的特解； (4)由初始条件确定待定系数； (5)得出解
特征方程没有重根
3.2 递推关系
分析：特征方程为x3 2x2 x 2 0, 特征根为x1 1, x2 1, x3 2
q是特征根 qn是解 1n 1, (1)n ,2n 是解，所以 un c1 c2 (1)n c3 2n 利用初始条件确定待定系数
特征方程没有重根
3.2 递推关系
3.2 递推关系
解：递推关系 an 3an1 3an2 an3 24n 6(n 3)的特征方程为 x3 3x2 3x 1 0, 特征根为 x1 x2 x3 1,故其通解为 an c1 c2 n c3n2 因为1是三重特征根，所以递推关系
an 3an1 3an2 an3 24n 6(n 3)有特解an n3( An B), 其中A, B是待定系数，代入上式得A 1, B 5,则 an c1 c2 n c3n2 n4 5n3, 其中c1, c2 , c3是待定系数， 由初始条件得 c1 4, c2 17, c3 21,所以 an 4 17n 21n2 n4 5n3
定理3.20设{ f (n)}n0是Fibonacci数列，则
f
(n)
[n] 2
k 0
n
k
k
(n
0,1,2,)
n
定理3.21 f (k) f (n 2) 1
k 0
定理3.22 f (n m) f (n) f (m) f (n 1)(m 1)
3.3Fibonacci数
例：求f (20) 解：f (20) f (10 10) f (10) f (10) f (9) f (9) 又f (10) f (5 5) f (5) f (5) f (4) f (4); f (9) f (5 4) f (5) f (4) f (4) f (3); f (3) 3, f (4) 5, f (5) 9; 所以, f (10) 89, f (9) 55, f (20) 10946
2k ff ((nn)) (Ef (nI )k 1f)(n)f ((En)I )2k 33n n1 2 3n 22 3n
设 ks
s f j10
f((n(1n)))kj2skjsf(E3nnj
3, 则n 1)
s
f
(n)
2s
3n1
2s
3n
2s1
3n
由 数jk0学(1归)k纳 j 法kj 知3n j
组基底。 ❖ 若A没有n个互异特征根时，若
mi重特征值 i有mi个线性无关的特征向量
有n个线性无关的特征向量做成一组基底。
特征方程有重根
3.2 递推关系
特征方程有重根
3.2 递推关系
特征方程有重根
3.2 递推关系
特征方程有重根
3.2 递推关系
特征方程有重根
3.2 递推关系
特征方程有重根
3.2 递推关系
常系数线性齐次递推关系
3.2 递推关系
常系数线性齐次递推关系
3.2 递推关系
常系数线性齐次递推关系
3.2 递推关系
常系数线性齐次递推关系
3.2 递推关系
常系数线性齐次递推关系
3.2 递推关系
❖ 解的线性组合还是递推关系的解，解集合做成解 空间。因此，仿效线性空间的知识，能否找到解 空间的一组基，如果能够找到，那么通解就有了。
k
f (nk)
3n
j0
2k
(1)k
3j nkj
3
j
3n (3 1)k 2k3n
3.1 差分 ❖
3.1 差分
3.1 差分
n
例3.2求和 k(k 1)(k 2) k 0
解：令f (n) n(n 1)(n 2),则f (n)是n的三次多项式且数列