组合数学讲义
【性质4】 设dn解，dn
2
是递推关系 ca
1
k
i
i 0
k
in i
n i
f1 n 的
是递推关系 ca
i 0
f2 n 的解，则
d
k
n
1 2 dn dn
是递推关系
cian i f1 n f2 n 的解。
i 0
§3.2.2 解的结构
（一） 概念
an c1an 1 c2an 2 ckan k 0,
定义3.2.1 称多项式 C(x)＝x
k
ck
0
(3.2.1)
c1xk 1 c2xk 2 ck 1x ck c1xk 1 c2xk 2 ck 1x ck＝0
为齐次递推关系（3.2.1）的特征多项式，相应的代数方程 C(x) ＝x
k
称为（3.2.1）的特征方程，特征方程的解称为（3.2.1）的特征根。
（二） 结论
【定理3.2.1】 数列an＝qn是（3.2.1）的非零解的充分必要条件是q为（3.2.1）的特征根。
（证） an＝qn是（3.2.1）的解 qn c1qn 1 ckqn k 0