《组合数学》 第三章 递推关系
?m?1?m?1?2m?j?2?j??r r??r＋r?????j?m?1??j?0?m?2?2m?2?＝r???jj?0?m?1j?j??r＝r??n?2??2????j?0?n?2???j?j?j??r＝ran?2 ?an＝an?1＋ran?2
当n为奇数时也成立。 求初值：a0＝a1＝1。则
a2＝a1＋ra0＝1＋r，a3＝a2＋ra1＝1＋2r， a4＝a3＋ra2＝(1＋2r)＋r (1＋r)＝1＋3r＋r2
a5＝a4＋ra3＝(1＋3r＋r2)＋r (1＋2r)＝1＋4r＋
3r2
【例3.1.4】设0出现偶数次的n位八进制数共有an个，0出现奇数次的数共有bn个。求an和bn满足的递推关系。 对0出现偶数次的n位八进制数分两种情况讨论：
（1）最高位是0，则其余n－1位应该含有奇数个0，这类八进制数共有bn?1个。
（2）最高位不是0，则其余n－1位还应该含有偶数个0，这类八进制数共有7an?1个。
因此有an＝7an?1＋bn?1。同理可得bn＝an?1＋7bn?1，所以an、bn满足
?an?7an?1?bn?1,?b?7bn?1?an?1, ?n??a1?7,b1?1例 n＝2
0出现偶数次的数 00，11，12，13，14，15，?，77，共50个
0出现奇数次的数 01，10，02，20，03，30，?，70，
6／72
《组合数学》 第三章 递推关系
共14个
x??y?y?,?【例3.1.5】用后退的Euler公式求常微分方程?y??y?0??1的数值解。
（解）函数y＝y(x)在点xn处的真值记为y(xn)，近似值记为yn，求数值解即利用数值方法求y(x)在处xn的近似值yn（n＝1,2,??）。
思想：以直代曲。
向前的Euler方法：yn?1?yn?hf?xn,yn?，其中h＝xn?1?xn称为步长。
向后的Euler方法：后退的Euler公式是指对常微分方程y??f?x,y?，当已知函数y在xn处的值时，可通过解代数方程yn?1?yn?hf?xn?1,yn?1?求得函数y在xn?1处的数值解yn?1，其中h＝xn?1－xn是自变量x的步长（n＝0,1,2,?）。
7／72
《组合数学》 第三章 递推关系
x已知原方程为y??f?x,y??y?2，代入Euler公式
y可得函数y的数值解为
??xn?1??yn?1?yn?h?yn?1?2?
y??n?1??y?1?0（五） 本章研究内容
1. 建模； 2. 求解。
§3.2 常系数线性递推关系
常系数的线性递推关系：
an?c1an?1?c2an?2??ckan?k?0,?ck?0? （3.2.1） 或
an?c1an?1?c2an?2??ckan?k?f?n?,?ck?0? （3.2.2）
分别称为k阶齐次递推关系和k阶非齐次递推关系。其中f(n)
8／72
《组合数学》 第三章 递推关系
称为自由项。
显然，式（3.2.1）至少有一个平凡解 an?0?n?0,1,2,??，而人们更关心的是它的非零解。
结论：对于常系数线性递推关系的定解问题，其解必是唯
一的。 求解方法：首推特征根法。
思想：来源于解常系数线性微分方程，因为两者在结构上很类似，所以其解的结构和求解的方法也类似。
§3.2.1 解的性质
?1??2?【性质1】设数列?bn?和?bn11n22n?rb???rb?也是（3.2.1）之解。其中r1、r2为任意常
数。
?1??2?（证）?bn，即 ?、?bn?满足方程（3.2.1）
?是（3.2.1）的解，则
?1??1??1??1?bn?c1bn?1?c2bn?2??ckbn?k?0, ① ?2??2??2??2?bn?c1bn?cb??cb?12n?2kn?k?0, ②
令r1×①＋r2×②得：
?1??2?r1?cibn?i?r2?cibn?i??ci?r1bn?rb?i2n?i??0
?1??2?i?0i?0i?0kkk（规定c0＝1，下同）。
?1??2??s?【推广】设bn均为（3.2.1）之解，,bn，?，bns??i??则?bn??ribn?也是（3.2.1）的解。其中r1,r2,?,rs为任意
i?1??常数。
??????9／72
《组合数学》 第三章 递推关系
??2??1?【性质2】设dn和dn是（3.2.2）的解，则
?1??2?是（3.2.1）的解。 bn?dn?dn?????【性质3】若?bn?是（3.2.1）的解，?dn?是（3.2.2）的解，
则?dn?bn?是（3.2.2）的解。
?1??2??s?一般情形：设?dn?是（3.2.2）的解，bn,bn，?，bns??i??分别是（3.2.1）的解，则?dn??bn?是（3.2.2）的解。
i?1??k???????2?【性质4】设dn是递推关系?cian?i?f1?n?的解，dn?1?i?0k?????1??2?是递推关系?cian?i?f2?n?的解，则?dn?dn?是递?dni?0推关系?cian?i?f1?n??f2?n?的解。
i?0k
§3.2.2 解的结构
（一） 概念
an?c1an?1?c2an?2??ckan?k?0,【定义3.2.1】称多项式
C(x)＝x?c1xkk?1?ck?0? （3.2.1）
?c2xk?2???ck?1x?ck
为齐次递推关系（3.2.1）的特征多项式，相应的代数方程
C(x) ＝x?c1xkk?1?c2xk?2???ck?1x?ck＝0
称为（3.2.1）的特征方程，特征方程的解称为（3.2.1）的特征根。
10／72