《组合数学》 第三章 递推关系
（四） 化非齐次方程为齐次方程 【例3.2.9】求sn??k。
k?0n?sn?sn?1?n,（解）（1）sn满足的递推关系 ?
?s0?0注：不能用迭代法求解。 （2）化为齐次递推关系 改写递推关系
sn?sn?1?n ①
类似得
sn?1?sn?2?n?1 ②
①－②得
sn?2sn?1?sn?2?1 ③
同理
sn?1?2sn?2?sn?3?1 ④
?sn?3sn?1?3sn?2?sn?3?0,③－④得 ?
?s0?0,s1?1,s2?3规律：左边升阶，右边降阶。 （3）求解
特征根：q＝1是三重根。
nsn?A?Bn?Cn2?1?＝A?Bn?Cn2
??代初值?s0?0,s1?1,s2?3?：
?A?0??A?B?C?1 ?A?2B?3C?3?21／72
《组合数学》 第三章 递推关系
1∴ A＝0， B＝C＝
2112n?n?1?∴ sn?n?n＝
222用递推关系证明了求和公式
n?n?1? 1?2???n?2（五） 一般求和公式 （1）问题：求sn??r?rk? k?0n（2）化为齐次递推关系求解
首先，当r＝1时，由（四）知
sn?A?Bn?Cn2
当r＝2时，可得
sn?sn?1?n2 ①
sn?1?sn?2??n?1? ②
2①－②得
sn?2sn?1?sn?2?2n?1 ③ sn?1?2sn?2?sn?3?2?n?1??1 ④
③－④得
sn?3sn?1?3sn?2?sn?3?1 ⑤ sn?1?3sn?2?3sn?3?sn?4?1 ⑥
⑤－⑥就得关于sn的齐次定解问题
?sn?4sn?1?6sn?2?4sn?3?sn?4?0, ??s0?0,s1?1,s2?5,s3?14
特征根仍然是q＝1（四重），所以
sn?A?Bn?Cn2?Dn3
再利用初值条件得
n?n?1??2n?1? sn?622／72
《组合数学》 第三章 递推关系
（3）快速求常数A、B、C、D等 当r＝1时，令
sn＝A?Bn?Cn?n?1?
?A?0?代入初始条件后得 ?A?B?1
?A?2B?2C?3?11解得 A＝0，B＝1－A＝1，C＝(3－A－2B)＝
22
优点：不需要解线性代数方程组，即可逐步递推地解出系数A、B、C等。 另法：令
1n?n?1?∴ sn?n?n?n?1?? 22n?n?1?sn?A?Bn?C
2！?A?0?代入初值条件 ?A?B?1
?A?2B?C?3?解得 A＝0，B＝1－A＝1，C＝3－A－2B＝1
优点：在利用初值确定A、B、C时更加方便。因为方程中分别关于A、B、C的系数恰好是1，不做除法。 当r＝2时，可令
n?n?1?n?n?1??n?2?sn?A?Bn?C?D 2！3！代入初值?s0?0,s1?1,s2?5,s3?14?得方程组
23／72
《组合数学》 第三章 递推关系
?A?0?A?B?1? ??A?2B?C?5??A?3B?3C?D?14A＝0， B＝1， C＝3， D＝2
sn?n?3n?n?1?n?n?1??n?2?n?n?1??2n?1? ?2?266
?r?对于较大的r，求部分和sn时，利用非齐次递推关系
sn?sn?1?nr求解还是要比将其化为齐次递推关系方便得
多。
（4）一般情形
若通解an为r阶多项式Pr?n?，对定解问题（3.1.2），可令
?n??n??n? ????Pr?n??A0?A1??A???A2?r??1???????2??r?使得用初值条件求解常数Ai非常简单。 §3.2.5 一般递推关系化简
对于某些非线性或变系数的递推关系，可以将其化为线性关系来求解。
n??an?nean?1?0,【例3.2.10】解定解问题 ?
??a0?1.2（解）线性变系数一阶齐次关系。改写
an?nean?1
两边取对数： lnan?lnan?1?lnn?n2
n2?bn?bn?1?lnn?n2,令bn?lnan，得?
?b0?0.24／72
《组合数学》 第三章 递推关系
再令f1?n??lnn，f2?n??n2。化为两个递推关系
?bn?bn?1?n2,?bn?bn?1?lnn, 和 ? ??b0?0.?b0?0.?bn?bn?1?lnn,?1?用迭代法解?，得bn?lnn!，
?b0?0.?bn?bn?1?n2,n?n?1??2n?1??2?用待定系数法解?，得bn?。
6?b0?0.从而得
n?n?1??2n?1? bn?lnn!?6∴ an?e?ee?n?n?1??2n?1??a?n!?exp∴ n ??6??lnn!?n?n?1??2n?1?6n?n?1??2n?1?lnn!6
?nan??n?1?an?1?2n,【例3.2.11】解定解问题 ?a?273.0?（解）线性变系数一阶非齐次关系。
?bn?bn?1?2n,令bn?nan得 ?
b?0.?0n?1
通解为 bn?B??1?n2n?1?
32由初始条件b0?0 知 B??
322n?12nnn∴ bn????1???2???1?
3332n?na?2???1?,n?1?n∴ ? 3n?3?a0?27.5即a1?2,a2?1,a3?2,a4?,?.
2????25／72