《组合数学》 §2.1 学习笔记
2.1.1 ~ 2.1.2
略。
定理 2.2.3
定义斐波那契数列
fn={0n=01n=1fn−1+fn−2n≥2当 n≥0 时有
fn=1√5(1+√52)n−1√5(1−√52)n证明略。
例 2.1.4
略。
定义 2.1.5
称数列 {hn}∞n=0 满足 k 阶常系数线性齐次递推关系，若对所有的 n≥k ，有
hn=a1hn−1+a2hn−2+⋯+akhn−k其中 ak≠0 (k≥1) 为常数。
设 q 为非零复数，容易看出，hn=qn 是上述 k 阶常系数线性齐次递推关系的解当且仅当 q 是 k 次多项式方程
g(x)=xk−a1xk−1−⋯−ak−1x−ak=0的根。称方程 g(x)=xk−a1xk−1−⋯−ak−1x−ak=0 为上述常系数线性齐次递推关系的特征方程。
定理 2.1.6
若 k 阶常系数线性齐次递推关系
hn=a1hn−1+a2hn−2+⋯+akhn−k,ak≠0 (k≥1)的特征方程 g(x)=0 有 k 个互不相同的根 q1,q2,⋯,qk ，则
hn=c1qn1+c2qn2+⋯+ckqnk,n≥0是下述意义下的一般解：无论给定怎样的初始值 h0,h1,⋯hk−1 ，
都存在相应的常数 c1,c2,⋯ck 使得上式是满足递推关系和初始条件的为一数列。
证明略。
例 2.1.7
由字母 a,b,c 组成的长度为 n 的字符串在通信信道上传送，满足条件：
不得有两个 a 连续出现在任一字符串中。确定通信信道允许传送的字符串个数。
解 记 hn 为允许传送的长度为 n 的字符串个数，则 h1=3,h2=8 。
考虑长度为 n 的最后一个符号，若其不为 a ，则有 2hn−1 个字符串；
反之则倒数第二个符号不一定是 a ，故此时有 2hn−2 个字符串。故当 n≥2 时，有
hn=2hn−1+2hn−2不妨定义 h0=1 ，因为这也满足上述递推关系。解特征方程
x2−2x−2=0得到根
q1=1+√3,q2=1−√3于是可设 hn 为
hn=c1(1+√3)n+c2(1−√3)n其中 c1,c2 为待定系数。通过初始条件 h0=1,h1=3 解得
c1=2+√32√3,c2=−2+√32√3故
hn=2+√32√3(1+√3)n+−1+√32√3(1−√3)n下面给出比定理 2.1.6 更为一般的结论
定理 2.1.8
设 k 阶常系数线性齐次递推关系
hn=a1hn−1+a2hn−2+⋯+akhn−k,ak≠0 (k≥1)的特征方程
g(x)=xk−a1xk−1−⋯−ak−1x−ak=0有互异根 q1,q2,⋯,qt ，其中 qi 是 si 重根 (1≤i≤t,s1+s2+⋯st=k) ，则
hn=t∑i=1Pi(n)qni是该递推关系的一般解，其中 Pi(n) 是关于 n 的次数小于 si 的多项式。
例 2.1.9
求解线性齐次递推关系
hn=−hn−1+3hn−2+5hn−3+2hn−4,n≥4初始条件为 h0=1,h1=0,h2=1,h3=2 。
解 由上述定理，解特征方程
x4+x3−3x2−5x−2=0得到根 q1=−1 （3重）和 q2=2 。于是可设 hn 为
hn=(c1n2+c2n+c3)(−1)n+c42n其中 c1,c2,c3,c4 为常数。通过初始条件 h0=1,h1=0,h2=1,h3=2 解得
c1=0,c2=−39,c3=79,c4=29所以
hn=(79−3n9)(−1)n+29⋅2n
