组合数学讲义
当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 7b
n 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，共14个
x
y y ,
例3.1.5 用后退的Euler公式求常微分方程 y
y 0 1