35th Putnam 1974

------
 
 
Problem A4

Find 1/2n-11[n/2] (n - 2i) nCi, where nCi is the binomial coefficient.

 

Solution

Answer: n( (n-1)C[n/2] - 1)/2n-1

It suffices to show that ∑0[n/2] (n - 2i) nCi = n ( (n-1)C[n/2] ).

We need two obvious facts: i nCi = n (n-1)C(i-1) (use factorials) and ∑0[n/2] nCi = 2n-1 if n is odd, or 2n-1 + 1/2 nC[n/2] if n is even (use nCr = nC(n-r) ).

So consider first n odd. ∑0[n/2] (n - 2i) nCi = n 2n-1 - 2 ∑0[n/2] i nCi = n 2n-1 - 2n ∑1[n/2] (n-1)C(i-1). Taking out the factor n we have 2n-1 - 2 ∑0[n/2]-1 (n-1)Ci = 2n-1 - (2n-1 - (n-1)C[n/2] ) = (n-1)C[n/2], as required.

Similarly for n even, we have ∑0[n/2] (n - 2i) nCi = n (2n-1 + 1/2 nC[n/2] ) - 2n ∑0[n/2]-1 (n-1)Ci = n/2 ( nC[n/2] ) = n! / ( [n/2}! ([n/2]-1)! ) = n (n-1)C[n/2], as required.

 


 

35th Putnam 1974

© John Scholes
jscholes@kalva.demon.co.uk
18 Aug 2001