《组合数学》 第三章 递推关系
?an?2an?1?2an?2?0【例3.2.4】求定解?。
?a0?0,a1?1（解）特征方程： q2－2q＋2＝0
2?4?8特征根： q＝＝1±i
2（方法I）按复根形式：??2，???4n?n?n???Bsin通解： an＝2?Acos? 44???A?0?代初值： ?? 22???2??A2?B2??1???解： A＝0，B＝1
nn?定解： an?2sin
4?0,当n?4m?m＝???1?22m,当n?4m?1，m＝0,1,? ?m2m?1???12,当n?4m?2,4m?3?数列：0，1，2，2，0，-4，-8，-8，0，16，-32，-32，?
????（方法II）按单根形式：
nn通解： an?A?1?i??B?1?i?
i?A????A?B?0?2代入初值： ?， 即?
??1?i?A??1?i?B?1?B?i??2iinn定解： an???1?i???1?i?
22化复数表示形式为实数形式 n?in?n?an??2?cos?isin244????? ?16／72
《组合数学》 第三章 递推关系
?＝?ii2n?n???2??cos?isin??
44n???2?isinn4＝??n?nn? 2sin4【例3.2.5】求定解
?an??4?i?an?1??5?4i?an?2??4?5i?an?3??4?4i?an?4?4ian?5?0 ??a0?5,a1?6,a2?10,a3?24,a4?50（解）特征方程：
q5??4?i?q4??5?4i?q3??4?5i?q2??4?4i?q?4i＝0
特征根： q＝2，2，i，i，－i
通解： an＝?A?Bn?2n??C?Dn?in?E??i?
n?A?C?E?5?2?A?B???C?D?i?E(?i)?6??代初值： ?4?A?2B???C?2D??E?10
?8?A?3B???C?3D?i?Ei?24???16?A?4B???C?4D??E?50解： A＝3，B＝0，C＝1，D＝0，E＝1 定解： an＝3?2n?in???i?n
n/2n??3?2?2??1?,当n?4m,4m?2＝?， n??3?2,当n?4m?1,4m?3n＝0,1, ?
（四） 代数方程求根
方程：anx?an?1xnn?1??a1x?a0＝0，在复数域上
必有n个根x1,x2,?,xn（k重根按k个算）。
17／72
《组合数学》 第三章 递推关系
?na0?x1x2?xn???1?a?n（1）韦达定理 ?
?x?x???x??an?112n?an?（2）推论：例3.2.1中，方程x3?4x2?x?6?0若有整数
根，则此根必整除-6，即此根必为±1，±2，±3，±6之一。 （3）方程的降阶：由韦达定理知-1是解，方程必可分解为
?x?1?x2?ax?b＝0
??§3.2.4 非齐次方程
（一） 结构
困难性：与微分方程类似。 可解情形：f(n)的几种特殊情形。
an?c1an?1?c2an?2??ckan?k?0 （3.2.1） an?c1an?1?c2an?2??ckan?k?f?n? （3.2.2）
【定理3.2.2】设an是（3.2.2）的一个特解，an是（3.2.1）的通解，则（3.2.2）的通解为
*an?an?an
*（证）（1）an是解；（2）an是通解。（类似齐次情形） 意义：问题归结为求非齐次递推关系的特解。 （二） 待定系数法
*目的：求特解an
困难：无一般通用方法
特例：当自由项f(n)比较简单时，采用待定系数法 （一）f(n)＝b（b为常数）
18／72
《组合数学》 第三章 递推关系
*an?Anm
*m表示1是m重特征根。若1不是特征根（即m＝0），则an＝A。
n（二）f?n??b（b为常数）
*an＝Anmbn
*m表示b是m重特征根。若b不是特征根，则an?Abn。
（三）f?n??bnPr?n?，其中Pr?n?为关于n的r次多项式，b为常数。
*an＝nmbnQr?n?
Qr?n?是与Pr?n?同次的多项式，m是b为特征根的重数。当
*b不是特征根时，an?bnQr?n?。 （三） 例
【例3.2.6】求非齐次方程an－13 an－2＋12an－3＝3的通解。 （解）分析：方程右边为常数3 特征方程： q3－13q＋12＝0 特征根： q＝1，3，-4，m＝1
*特解： an＝An（A称为待定系数）
代入递推关系： An－13A(n－2)＋12A(n－3)＝3
整理得 －10A＝3 解之 A＝?3，故为 103n。其中B1、B2、B3为任10通解：an＝B1＋B23 n＋B3(－4) n－
意常数。
【例3.2.7】求递推关系an－4 an－1＋4an－2＝2n 的通解。 （解）分析：方程右边为2n
19／72
《组合数学》 第三章 递推关系
特征根： q＝2（二重根），
*特解： an＝An2 2n
代入原式：An22n－4A?n?1?2n?1＋4A?n?2?2n?2＝2n
22展开：An22n－2A(n2－2n＋1)22n＋A(n2－4n＋4)22n＝2n
整理： 2A2n＝2n 待定系数： A＝1
2
12?n12n?nna通解：n＝B12＋B2n2＋n2＝?B1?B2n?n?2。
2?2?其中B1、B2为任意常数。 【例3.2.8】求an＋4an－1＋an－2＝n(n－1) 的通解。 （解）分析：方程右边为多项式：f(n)＝n2－n（b＝1） 特征根： q＝－2±3（b＝1不是特征根）
*特解： an＝An2 ＋Bn＋C
代入原方程：
?An2?Bn?C?＋4A?n-1??B?n-1??C
2??＋A?n-2??B?n-2??C＝n(n－1)
2??整理： 6An2 －6(2A－B)n＋2(4A－3B＋3C)＝n2－n 比较两边同类项的系数：
?6A?1???6?2A?B???1 ?2?4A?3B?3C??0?111解得 A＝，B＝，C＝?
66181nn?通解：an＝B1q1＋3n2?3n?1?。其中B1、B2为?B2q218任意常数。
20／72