Advanced book on Mathematics Olympiad

6.2 Binomial Coefficients and Counting Methods 299

The Laplace transform applied to the differential equation

y′′+uy′+vy= 0

produces the algebraic equation

s^2 L(y)−y′( 0 )−sy( 0 )+u(sL(y)−y( 0 ))−vL(y)= 0 ,

with the solution

L(y)=

sy( 0 )+uy ( 0 )+y′( 0 )

s^2 +us+v

.

Again the partial fraction decomposition comes in handy, since we know that the inverse
Laplace transforms ofs−^1 r 1 ands−^1 r 2 areer^1 xander^2 x. The similarity of these two methods
is not accidental, for recursive sequences are discrete approximations of differential
equations.
Let us return to problems and look at the classical example of the Catalan numbers.

Example.Prove that the number of ways one can insert parentheses into a product of

n+1 factors is the Catalan numberCn=n+^11

( 2 n

n

)

.

Solution.Alternatively, the Catalan numberCnis the number of ways the terms of the

product can be grouped for performing the multiplication. This is a better point of view,

because the location of the final multiplication splits the product in two, giving rise to

the recurrence relation

Cn=C 0 Cn− 1 +C 1 Cn− 2 +···+Cn− 1 C 0 ,n≥ 1.

Indeed, for everyk= 0 , 1 ,...,n−1, the firstk+1 terms can be grouped inCkways,

while the lastn−kterms can be grouped inCn−k− 1 ways. You can recognize that the

expression on the right shows up when the generating function is squared. We deduce

that the generating function satisfies the equation

G(x)=xG(x)^2 + 1.

This is a quadratic equation, with two solutions. And because limx→ 0 G(x)=a 0 ,we

know precisely which solution to choose, namely

G(x)=

1 −

√

1 − 4 x

2 x

.

Expanding the square root with Newton’s binomial formula, we have

√

1 − 4 x=( 1 − 4 x)^1 /^2 =

∑∞

n= 0

(

1 / 2

n

)

(− 4 x)n=

∑∞

n= 0

(^12 )(^12 − 1 )···(^12 −n+ 1 )

n!

(− 4 x)n