Advanced book on Mathematics Olympiad

298 6 Combinatorics and Probability

865.Prove the analogue of Newton’s binomial formula

[x+y]n=

∑n

k= 0

(

n

k

)

[x]k[y]n−k,

where[x]n=x(x− 1 )···(x−n+ 1 ).

866.Prove that the quantum binomial coefficients

(n

k

)

qpreviously defined satisfy

∑n

k= 0

(− 1 )kq

k(k 2 − 1 )

(

n

k

)

q

= 0.

6.2.2 Generating Functions

The terms of a sequence(an)n≥ 0 can be combined into a function

G(x)=a 0 +a 1 x+a 2 x^2 +···+anxn+···,

called the generating function of the sequence. Sometimes this function can be written

in closed form and carries useful information about the sequence. For example, if the

sequence satisfies a second-order linear recurrence, sayan+ 1 +uan+van− 1 =0, then

the generating function satisfies the functional equation

G(x)−a 0 −a 1 x+ux(G(x)−a 0 )+vx^2 G(x)= 0.

This equation can be solved easily, giving

G(x)=

a 0 +(ua 0 +a 1 )x

1 +ux+vx^2

.

Ifr 1 andr 2 are the roots of the characteristic equationλ^2 +uλ+v=0, then by using

the partial fraction decomposition, we obtain

G(x)=

a 0 +(ua 0 +a 1 )x

( 1 −r 1 x)( 1 −r 2 x)

=

α

1 −r 1 x

+

β

1 −r 2 x

=

∑∞

n= 0

(αr 1 n+βr 2 n)xn.

And we recover the general-term formulaan=αr 1 n+βr 2 n,n≥0, whereαandβdepend
on the initial condition.
It is useful to notice the analogy with the method of the Laplace transform used for
solving linear ordinary differential equations. Recall that the Laplace transform of a
functiony(t)is defined as

Ly(s)=

∫∞

0

y(t)etsdt.