母函数方法在解竞赛题中的运用

●

(杭州第十一中学 浙江杭州 310053)

母函数方法的实质是将离散数列和幂级数一一对应起来，把离散数列间的相互结合关系对应成为幂级数间的运算关系，最后由幂级数形式来确定离散数列的构造的一种方法．具体地说，就是将一个有限或无限的数列{ak}和形如f(x)=a0+a1x+a2x2+…+akxk+…的函数联系起来，构成对应关系.将其中的f(x)称为数列{ak}的母函数或生成函数，意思是这个数列{ak}是由多项式f(x)生成的．母函数方法一般在解组合问题中应用较多，本文将母函数方法进行推广，通过一些竞赛试题说明它在解方程(方程组)、解操作性问题、解多元求值问题、证明组合恒等式等诸多方面的应用．

1 解方程或方程组

解构造母函数f(x)=(x-x1)(x-x2)…(x-xn)，并设f(x)=xn+an-1xn-1+…+a1x+a，则

即

n+nan-1+…+na1+na0=0,

亦即

1+an-1+…+a1+a0=0，

故f(1)=0．

这说明x=1是方程f(x)=0的一个根，由对称性，不妨设xn=1，代入方程组中可得

同理可解得x1=x2=…=xn-1=xn=1．

2 求数列的通项公式

例2已知在数列{an}中，a0=-1，a1=1,an=2an-1+3an-2+3n(n≥2),求数列的通项an．

解考虑母函数f(x)=a0+a1x+a2x2+…+anxn+…，则

-2xf(x)=-2a0x-2a1x2-2a2x3-…-2an-1xn+…

-3x2f(x)=-3a0x2-3a1x3-3a2x4-…-3an-2xn+…

以上3个式子相加，又a0=-1，a1=1,an=2an-1+3an-2+3n(n≥2),化简得

3 解操作性问题

例3设a1,a2,…,a100,b1,b2,…,b100为互不相同的实数，将它们依如下规则填入100×100的方格中:在第i行和第j列相交处的方格内填入数字ai+bj．已知每一列的所有数字乘积都等于1，证明:每一行的所有数的乘积都等于-1．

证明构造母函数f(x)=(x+a1)(x+a2)…(x+a100)-1，则多项式f(x)的次数为100，且f(x)的首项系数为1．依题意知f(bi)=0(i=1,2,…,100)，从而x-bi(i=1,2,…,100)都是f(x)的因式．因为b1,b2,…,b100互不相同，所以f(x)=(x-b1)(x-b2)…(x-b100),即

(x+a1)(x+a2)…(x+a100)-1=(x-b1)(x-b2)…(x-b100).

在上式中，令x=-ai(i=1,2,…,100)，则

-1=(-1)100(a1+b1)(a2+b2)…(a100+b100),

故第i行中所有数的乘积都等于-1．

4 解多元求值问题

例4设x,y,z与w适合:

求x2+y2+z2+w2的值．

(t-1)(t-9)(t-25)(t-49)-x2(t-9)(t-25)(t-49)-y2(t-1)(t-25)(t-49)-

z2(t-1)(t-9)(t-49)-w2(t-1)(t-9)(t-25)=0,

整理得

t4-(1+9+25+49+x2+y2+z2+w2)t3+f(t)=0,

其中f(t)是次数不超过2的多项式，上述方程是关于t的四次方程，它有4个根:4，16，36，64.由韦……