《组合数学》 第三章 递推关系
（二） 结论
【定理3.2.1】数列an?qn（3.2.1）的非零解的充分必要条件是q为（3.2.1）的特征根。 （证）an?qn是（3.2.1）的解
?qn?c1qn?1???ckqn?k?0 ?qk?c1qk?1???ck?0
?q是方程C(x)＝0的根，即q是（3.2.1）的特征根。
意义：将求解常系数线性齐次递推关系的问题转化为常系数代数方程的求根问题，从而给出了一个实用且比较简单的解此类递推关系的方法。 （三） 通解
?1??2??s?【定义3.2.2】 若an是（3.2.1）的不同,an,?,an解，且（3.2.1）的任何解都可以表为?1??2??s?r1an?r2an???rsan?an，则称an为（3.2.1）的通解。其
??????中r1,r2,?,rs为任意常数。
?i?此处所说的不同解是指将每一个解an都视为一个无穷维的解向量，而这些向量之间是线性无关的。
??说明 通解的特征：
① 通解an首先是解；
② 组成通解的所有解向量线性无关；
③ 任何一个具体的解都被包容在通解an中。
§3.2.3 特征根法
思路：通过解式（3.2.1）的特征方程，求得其特征根，再利用特征根构造（3.2.1）的通解。
11／72
《组合数学》 第三章 递推关系
（一） 特征根为单根情形
设q1,q2,?,qk是（3.2.1）的互不相同的特征根，则（3.2.1）的通解为
nnnan?A1q1?A2q2???Akqk （3.2.3）
其中A1,A2,?,Ak为任意常数（待定）。
（证）（1）an是（3.2.1）的解：由定理3.2.1知qi是方
程（3.2.1）的解，再由性质1知an也是（3.2.1）的解。
nnn（2）向量q1线性无关： ,q2,?,qkn????k??（3）（3.2.1）的所有解都可以表为（3.2.3）的形式：设bn是（3.2.1）的一个解，且满足初始条件bi?di，i＝0, 1, 2, ?, k－1。令bn?程组
000?A1q1?A2q2???Akqk?b0??A1q1?A2q2???Akqk?b1 （3.2.4） ???????Aqk?1?Aqk?1???Aqk?1?b22kkk?1?11?Aiqin，代入初始条件，得关于A的线性方
ii?1系数行列式为范德蒙行列式：
1q12D?q1?1q22q2????2qk???qj?qi??0
1?i?j??k?1qkk?1k?1k?1q1q2?qk所以式（3.2.4）有唯一解。即bn一定可以表示为（3.2.3）的形式。
由于bn的任意性，故知结论成立。
12／72
《组合数学》 第三章 递推关系
【例3.2.1】求递推关系an?4an?1?an?2??6an?3的通解。 （解）特征方程为x3?4x2?x?6?0，解之得特征根
q1＝－1， q2＝2，q3＝3
∴ 通解为 an?A??1??B2n?C3n
n其中，A、B、C为任意常数。
若是定解问题，设初值为：a0?5，a1?13，a2?35，带入通解得
?A?B?C?5???A?2B?3C?13 ?A?4B?9C?35?解得A＝0，B＝2，C＝3，故
an?2?2n?3?3n?2n?1?3n?1
若初值为a0?4，a1＝－1，a2＝7，则
an?3??1??2n
n求A、B、C的方程组为
?A?B?C?4???A?2B?3C??1 ?A?4B?9C?7?规律： （二） 重根情形
【例3.2.2】求递推关系an?4an?1?4an?2?0的通解。
13／72
《组合数学》 第三章 递推关系
（解）特征方程x2?4x?4?0 特征根 q1?q2?2（二重根）
仿单根情形 an＝A12n?A22n＝?A1?A2?2n＝A2n
一个待定常数。
问题：满足两个初始条件a0?d0,a1?d1不太可能。 实质：两个解向量an?2和an?2是线性相关的。
?1??2?任务：找两个线性无关的解向量an和an。
?1?n?2?n?1??2?另一解：令an?2n线性无关。 ?n2n，也是解，且与anan?4an?1?4an?2
＝n2n－4(n－1)2n?1＋4(n－2)2n?2＝0
?1??2?10a0a0＝2 ?1??2??22a1a1nn通解： an?A12?A2n2（需证明）
一般情形：设q为k重根，则通解为 更一般的情形：有t
an??A1?A2n???Aknk?1?qn
个根，qi为ki重根
???i?1,2,?,t;?t?ki?k???。通解 i?1?kitan???Aijnj?1qin
n?A11?A12n???A1k1nk1?1q1
?i?1j?1n?A21?A22n???A2k2nk2?1q2
?????At1?At2n???Atktnkt?1qtn
【例3.2.3】求an?7an?1?19an?2?25an?3?16an?4?4an?5＝0的通解。
（解）特征方程 x5?7x4?19x3?25x2?16x?4＝0 特征根： x＝1（三重），x＝2（二重）
14／72
???《组合数学》 第三章 递推关系
通解 an＝(A11＋A12n＋A13n2)1n＋( A21＋A22n)2n
＝(A11＋A12n＋A13n2)＋( A21＋A22n)2n
（三） 复根情形
设特征方程有一对共轭（单）复根：q??ei?，q??e?i?，则通解中含
Aqn?Bq＝A?nein??B?ne?in?
＝A?n?cos?n???isin?n???＋B?n?cos?n???isin?n??? ＝?A?B??ncos?n??＋i?A?B??nsin?n?? ＝A1?ncos?n??＋A2?nsin?n??
通解： an＝A1?ncos?n???A2?nsin?n????
优点：避免了复数运算。尤其是当数列{an}是实数时，
nAqn?Bq的虚部为零。
一般情形：q是m重复根，q也是m重复根，通解中有
n?n??A1?A2n???Amnm?1?cos?n??＋?B1?B2n???Bmnm?1?sin?n???
小结： 特征根 q为单根 m重根 一对单复根 q??ei? ,1实根?A?An???An?qm?12m通解中对应的项 Aqn n ?n?A1cos?n???A2sin?n??? ?n?A1?A2n???Amnm?1?cos?n?? ??B1?B2n???Bmnm?1?sin?n?? 复根q??e?i? 一对m重复根 q??ei? ,q??e?i? 15／72