Advanced book on Mathematics Olympiad

300 6 Combinatorics and Probability

= 1 −

∑∞

n= 1

( 2 n− 3 )( 2 n− 5 )··· 1

n!

( 2 x)n= 1 − 2

∑∞

n= 1

( 2 n− 2 )!

(n− 1 )!(n− 1 )!

xn

n

= 1 − 2

∑∞

n= 1

(

2 n− 2

n− 1

)

xn

n

.

Substituting in the expression for the generating function and shifting the index, we obtain

G(x)=

∑∞

n= 0

1

n+ 1

(

2 n

n

)

xn,

which gives the formula for the Catalan numberCn=n+^11

( 2 n

n

)

. 

The binomial coefficients

(n

k

)

are generated by a very simple function, G(x) =

(x+ 1 )n, and variations of this fact can be exploited to obtain combinatorial identi-

ties. This is the case with a problem published in theAmerican Mathematical Monthly

by N. Gonciulea.

Example.Prove that

∑n

j= 0

(

n

j

)

2 n−j

(

j

j/ 2 

)

=

(

2 n+ 1

n

)

.

Solution.Observe that

( j

j/ 2 

)

is the constant term in( 1 +x)(x−^1 +x)j. It follows that

the sum is equal to the constant term in

∑n

j= 0

(

n

j

)

2 n−j( 1 +x)(x−^1 +x)j

=( 1 +x)

∑n

j= 0

(

n

j

)

(x−^1 +x)j 2 n−j=( 1 +x)( 2 +x−^1 +x)n

=

1

xn

( 1 +x)( 2 x+ 1 +x^2 )n=

1

xn

( 1 +x)^2 n+^1.

And the constant term in this last expression is

( 2 n+ 1

n

)

. 

867.Find the general-term formula for the sequence(yn)n≥ 0 withy 0 =1 andyn =

ayn− 1 +bnforn≥1, whereaandbare two fixed distinct real numbers.

868.Compute the sums

∑n

k= 1

k

(

n

k

)

and

∑n

k= 1

1

k+ 1

(

n

k

)

.