发生函数的一些应用
主要工作如下：1、简单介绍了发生函数的定义及性质；2、利用发生函数推导出 Fibonacci数列的通项公式；3、给出一些递推关系的解；4、证明一些组合恒等式；5、利用拉格朗日反演公式证明组合恒等式；关键词 发生函数；Fibonacci数列；递推关系；组合恒等式；拉格朗日反演定理1、引言发生函数又称生成函数、母函数，是组合数学中的一个重要理论和工具.早在 1730 年，DeMoivre就利用发生函数讨论了斐波拉契数列.1812年，在《概率的分析理论》中，Laplace明确提出了发生函数的计算.在这一书中，Laplace 还深入研究了自然数的分拆和合成，对Euler的研究做了延伸和拓展.此后，发生函数的理论建立起来.1990年，Herbert Saul Wilf在《Generating Functionology》中论述了发生函数的各种作用：求数列的通项公式；求解递推关系；证明组合恒等式等.本文着重研究发生函数的一些应用.2、发生函数发生函数分为普通型发生函数和指数型发生函数两种，本文研究普通型发生函数.2.1发生函数的定义对于数列 n a a a a , , , , 2 1 0 ，我们则称幂级数 nnnnn x a x a x a x a a x a x G 3322 1 00) (是这个数列的发生函数. 2.2发生函数的性质已知 ) (x f 是数列 ｝ ｛ n a 的发生函数： nnx a x a x a a x f22 1 0 ) ( ， ) (x g 是数列｝ ｛ n b 的发生函数： nnx b x b x b b x g 22 1 0 ) (.那么我们有下面的性质：（1） nnn nnnnnnn x b a x b x a x g x f 0 0 0) ( ) ( ) (；（2） nnnnnnnnn x c x b x a x g x f 0 0 0) ( ) ( ，其中 ) (0k nkk n b a c ；（3）如果 0 ' f ，则 0 a f 是一个常数；（4）如果 f f '，则有 xce x f ) (；（5）以下是常用的几个数列及其对应的发生函数（其中 为任意实数） ：① xx a x f annn n 11) ( 10② 20 ) 1 () (xxx a x f n annn n ③ xx a x f annnnn 11) (0④ ) 1 ( ) (0x x a x fnannn n（6） .3、发生函数的应用3.1 Fibonacci数列Fibonacci数列是由意大利数学家斐波拉契提出的兔子繁衍问题引发而生的.斐波拉契是 12世纪欧亚之间数学交流的重要使者.斐波拉契在《计算之书》中提出了著名的兔子繁衍的问题，即：若是每一对成年兔子每月生一对一雌一雄的幼兔，幼兔经过两个月成为成兔，可以开始繁殖，那么年初的一对兔子在假设没有疾病或死亡的情况下，一年后能繁衍成多少对兔子？四百多年后，荷兰数学家吉拉尔注意到兔子繁衍的数列问题满足递推关系：2 1 n n n F F F ，这个数列后来被命名为 Fibonacci 数列.Fibonacci 数列应用广泛，美国0 1 2 3 2 3(1 )n n nn n n n nx x x x x C C C C C 数学会从 1963 年起出版了《斐波那契数列季刊》 ，用于专门刊登这一方面的研究成果.3.1.1 Fibonacci 数列的定义Fibonacci 数列：0，1，1，2，3，5，8，13，21，34，55，89，......第 0 项是 0，第 1项是第一个 1，从第 2 项开始有 2 1 n n n F F F .3.1.2 利用发生函数推导 Fibonacci 数列的通项公式对于 Fibonacci数列 n F ，有 1 2 1 F F ， ) 2 ( 2 1 n F F F n n n ，令数列的生成函数为 nnx F x F x F x F 22 1 ) ( ，那么，就有 x x F F F x F F x F x x x F nn n n • ) ( ) ( ) 1 ( ) ( 2 121 2 12，因此 21) (x xxx F .)25 11 )(25 11 ( 1 2x x x x ,） （x xx S25 11125 11151) (• .再利用展开式 nx x x xx3 2111，因此可以得到： .3.2利用发生函数对幂级数求和例、求和： ) , 2 , 1 , 0 ( ,0 nk nkk.解：用 f(n)表示该和式为 ) , 2 , 1 , 0 ( , ) (0 nk nkn fk， • n nn F25 125 151令 k nn kkk nnnnxk nkxk nkx n f x x F 0 0) ( ) (，由性质中：当 nan 时，其发生函数是： ) 1 ( ) (0x x a x fnnn .2020 0 11) ( ) 1 ( ) (x xx x x x xk nkx x Fkk kkk k nn kk ，此函数我们很熟悉，它由 Fibonacci 数列 } { n F 生成，故) , 2 , 1 ( ) (0 n Fk nkn f nk，.3.3 发生函数在递推关系中的应用3.3.1常系数线性齐次递推关系式的求解对于数列 : 当 时，有 ， ， ， n 为正整数.求此递推关系的解.解：定义数列的发生函数是：) ( ) ( ) () ( ) ) ( () () (220222221122 121 00x G Bx Ax x Aa b ax G Bx a x G Ax bx ax a Bx x a Ax bx ax Ba Aa bx ax a x a a x a x Gnnnnnnnnn nnnnnnn x Aa b a x G Bx Ax ) ( ) ( ) 1 (2 ①若 ，即 ，则：，其中 ，则此递推关系的解为： .②若 ，即 ，则： .由 ，求得： . n a 2 1 n n n Ba Aa a 2 n a a 0 b a 11 1 2 2 [ ] ( )n n nn a x G x r r 24,24 2221B A ArB A Ar 0 4 2 B A2 1122 121 ,r rb arr rar b x r x r Bx Axx Aa b ax G221121 1 1) () ( 22 1Ar r r 0 4 2 B Ann r n C C a ) ( 2 1 AAa bC a C 22 1 ， b a a a 1 0 ，