§22递推关系 因为:H(x)=∑h(k)x2 h(k)=2-1
§2.2 递推关系 因为： = = 1 ( ) ( ) k k H x h k x ( ) = 2 −1 k h k
§22递推关系 例2求n位十进制数中出现偶数个5的数 的个数。 先从分析n位十进制数出现偶数个5的数的 结构入手P12…Pn是n-1位十进制数,若含 有偶数个5,则Pn=1取5以外的0,1,2,3,4 6,7,8,9个数中的一个,若P1P2…Pn21 只有奇数个5,则取n=5,使p1D2…pn1Pn 成为出现偶数个5的十进制数
§2.2 递推关系 例2. 求n位十进制数中出现偶数个5的数 的个数。 先从分析n位十进制数出现偶数个5的数的 结构入手 是n-1位十进制数，若含 有偶数个5，则 取5以外的0，1，2，3，4， 6，7，8，9九个数中的一个，若 只有奇数个5，则取 ，使 成为出现偶数个5的十进制数。 p1 p2 pn−1 pn−1 p1 p2 pn−1 pn = 5 p1 p2 pn−1 pn
§22递推关系 解法1 令an=n位十进制数中出现5的数的个数, b.=n位十进制数中出现奇数个5的数 的个数 故有 a.=9a.,+b b.=9b.,+a → n-1 (2-2-2)
§2.2 递推关系 解法1： 令 位十进制数中出现5的数的个数， 位十进制数中出现奇数个5的数 的个数。 an = n b n n = 故有： an = 9an−1 +bn−1 bn = 9bn−1 + an−1 { a1 = 8, b1 =1 (2 − 2 − 2)
§22递推关系 2-2-2)式中的an=9an表达了含有偶数 个5的n位十进制数的两个组成部分 9a.表达由含有偶数个的n-1位十进制数 np2n,令取以外的0,1,2,3,4,6, 7,8,9九个数中的一个数构成的。硕表示 当P.是含有奇数个5的n-1位十进制数 令而得Pn=5是含偶数个5的n位十进 制数。 9b.,+ 也有类似解释
也有类似解释。 §2.2 递推关系 (2-2-2)式中的 表达了含有偶数 个5的n位十进制数的两个组成部分。 表达由含有偶数个5的n-1位十进制数 ，令 取5以外的0，1，2，3，4，6， 7，8，9九个数中的一个数构成的。 项表示 当 是含有奇数个5的n-1位十进制数， 令 而得 是含偶数个5的n位十进 制数。 bn = 9bn−1 + an−1 an = 9an−1 +bn−1 1 9 n− a p1 p2 pn−1 pn n−1 b p1 p2 pn−1 pn = 5 p1 p2 pn
§22递推关系 2-2-2是关于序列和的连立关系。 设序列{an的母函数为A(x),序列{)的母 函数为B(x) A(x)=a,+a,x+aax+ B(x)=6,+b,x+bx4+ 9xAx)=-91x-9a2 : B(x)=-b,x-b (1-9x)4(x)-xB(x)=8
(2-2-2)是关于序列 和 的连立关系。 §2.2 递推关系 设序列 的母函数为 ，序列 的母 函数为 。 { }n a { }n b { }n a A(x) { }n b B(x) + − = − − − − = − − − = + + + = + + + 2 1 2 2 1 2 2 1 2 3 2 1 2 3 ) ( ) 9 ( ) 9 9 ( ) ( ) x B x b x b x x A x a x a x B x b b x b x 即： A x a a x a x ____________________________ (1−9x)A(x) − x B(x) = 8