Find 1/2^{n-1} ∑_{1}^{[n/2]} (n - 2i) nCi, where nCi is the binomial coefficient.

**Solution**

Answer: n( (n-1)C[n/2] - 1)/2^{n-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 = 2^{n-1} if n is odd, or 2^{n-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 2^{n-1} - 2 ∑_{0}^{[n/2]} i nCi = n 2^{n-1} - 2n ∑_{1}^{[n/2]} (n-1)C(i-1). Taking out the factor n we have 2^{n-1} - 2 ∑_{0}^{[n/2]-1} (n-1)Ci = 2^{n-1} - (2^{n-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 (2^{n-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.

© John Scholes

jscholes@kalva.demon.co.uk

18 Aug 2001