§22递推关系 因为:(x)=∑(k)x 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的数的 结构入手n12…Pn是n-1位十进制数,若含 有偶数个5,则Pn1取5以外的0,1,2,3,4 6,7,8,9九个数中的一个,若P1P2…Pn 只有奇数个5,则取Pn=5,使P1P2…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的数的个数 n位十进制数中出现奇数个5的数 的个数。 故有 9a.;+b 1-」 b.=9b.,+ (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=9a,表达了含有偶数 个5的n位十进制数的两个组成部分。 9a.表达由含有偶数个5的n-1位十进制数 1P2…p,令取5以外的0,1,2,3,4,6 7,8,9九个数中的个数构成的。硕表示 当P1是含有奇数个5的n-1位十进制数 而得Dn=5是含偶数个5的n位十进 制数。 bn=9bn-1+an也有类似解释
也有类似解释。 §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-22)是关于序列{和的连立关系 设序列{an的母函数为A(x),序列{bn的母 函数为B(x)。 即: A(=a,+a,x+asx+ B(x=b,+b,x+b3x+ 9x(x)=-9ax-9a,x2- xB(x)=-b,x-b,x (1-9x)A(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