Advanced book on Mathematics Olympiad

6.2 Binomial Coefficients and Counting Methods 303

Next, a combinatorial identity.

Example.Letmandnbe two integers,m≤n− 21. Prove the identity

n− 21

∑

k=m

(

n

2 k+ 1

)(

k

m

)

= 2 n−^2 m−^1

(

n−m− 1

m

)

.

Solution.The solution is a Fubini-type argument. Consider the setPof pairs(A, B),
whereAis a subset of{ 1 , 2 ,...,n}with an odd number of elementsa 1 <a 2 <···<
a 2 k+ 1 andBis a subset of{a 2 ,a 4 ,...,a 2 k− 2 ,a 2 k}withmelementsb 1 <b 2 <···<bm.
For a givenkthere are

( n

2 k+ 1

)

such subsetsA, and for eachAthere are

(k

m

)

subsetsB,
so the left-hand side of the identity is the number of elements ofPcounted by choosing
Afirst.
Let us count the same number choosingBfirst. Note that if(A, B)∈P, thenB
contains no pairs of consecutive numbers. More precisely,B ={b 1 ,b 2 ,...,bm}⊂
{ 2 , 3 ,...,n− 1 }withbi+ 1 −bi≥2.
FixB 0 , a set with this property. We want to count the number of pairs(A, B 0 )inX.
Choosec 0 ,c 1 ,...,cmsuch that

1 ≤c 0 <b 1 ,b 1 <c 1 <b 2 ,...,bi<ci<bi+ 1 ,...,bm<cm≤n.

Then for any subsetEof{ 1 , 2 ,...,n}{c 0 ,b 1 ,c 1 ,b 2 ,...,bm,cm}there is a uniqueA
such that(A, B 0 )∈PandE⊂A.
Indeed, if(A, B 0 )∈PandE⊂Awe have to decide whichci’s are inA. Since
the setDi ={x ∈A | bi <x<bi+ 1 }must contain an odd number of elements
for each 0 ≤ i ≤ m+1 (withb 0 =0,bm+ 1 = n+ 1 ), and the setDi is either
{x∈E|bi<x<bi+ 1 }or{x∈E|bi<x<bi+ 1 }∪{ci}, the parity condition on the
cardinality ofDidecides whethercibelongs toA. It is now clear that the number of pairs
(A, B 0 )inPis the same as the number of subsets of{ 1 , 2 ,...,n}{c 0 ,b 1 ,...,bm,cm},
and the latter is 2n−^2 m−^1.
How many subsetsBwithmelements of{ 2 , 3 ,...,n− 1 }do not contain consec-
utive numbers? IfB={b 1 <b 2 <···<bm}is such a set, letB′={b 1 − 1 ,b 2 −
2 ,...,bm−m}. It is easy to see thatB′is an (arbitrary) subset of{ 1 , 2 ,...,n−m− 1 }
withmelements, and for each such subsetB′ ={b′ 1 <b′ 2 <···<bm′}, by letting
bi=b′i+i, we obtain a setBas above. Hence the number of suchB’s is

(n−m− 1

m

)

, and by
choosingBfirst we count the number of elements inPas 2n−^2 m−^1

(n−m− 1

m

)

. The identity
is proved. 

Using similar ideas solve the following problems.

879.Find in closed form

1 · 2

(

n

2

)

+ 2 · 3

(

n

3

)

+···+(n− 1 )·n

(

n

n

)

.