2
$\begingroup$

Let n be a positive integer.

Prove that $$\sum_{i=1}^n 2i\binom{2n}{n-i}= n\binom{2n}{n}$$

$\endgroup$
  • 1
    $\begingroup$ And... what did you try? $\endgroup$ – Did Mar 23 '13 at 13:56
  • $\begingroup$ Have you tried reversing your summation order and see if you recognize anything? $\endgroup$ – J. M. is a poor mathematician Mar 23 '13 at 13:56
1
$\begingroup$

Here’s an alternative that requires a little less of a leap to get started, but a little more algebra later. Instead of pulling $2i=(n+i)-(n-i)$ out of thin air, substitute $k=n-i$:

$$\begin{align*} \sum_{i=0}^n2i\binom{2n}{n-i}&=\sum_{k=0}^{n-1}2(n-k)\binom{2n}k\\ &=2n\sum_{k=0}^{n-1}\binom{2n}k-2\sum_{k=0}^{n-1}k\binom{2n}k\\ &=2n\sum_{k=0}^{n-1}\binom{2n}k-4n\sum_{k=1}^{n-1}\binom{2n-1}{k-1}\\ &=2n\left(\sum_{k=0}^{n-1}\binom{2n}k-2\sum_{k=0}^{n-2}\binom{2n-1}k\right)\\ &=2n\left(\sum_{k=0}^{n-1}\binom{2n}k-\sum_{k=0}^{n-2}\left(\binom{2n-1}k+\binom{2n-1}{2n-1-k}\right)\right)\\ &=2n\left(\sum_{k=0}^{n-1}\binom{2n}k-\sum_{k=0}^{n-2}\binom{2n-1}k-\sum_{k=n+1}^{2n-1}\binom{2n-1}k\right)\\ &=2n\left(\sum_{k=0}^{n-1}\binom{2n}k-\left(2^{2n-1}-\binom{2n-1}{n-1}-\binom{2n-1}n\right)\right)\\ &=2n\left(\sum_{k=0}^{n-1}\binom{2n}k-2^{2n-1}+\binom{2n}n\right)\\ &=n\left(2\sum_{k=0}^{n-1}\binom{2n}k-2^{2n}+2\binom{2n}n\right)\\ &=n\left(2^{2n}-\binom{2n}n-2^{2n}+2\binom{2n}n\right)\\ &=n\binom{2n}n\;. \end{align*}$$

I still haven’t found a combinatorial argument, though.

$\endgroup$
5
$\begingroup$

\begin{align} \sum_{i=1}^{n}{2i\binom{2n}{n-i}} & =\sum_{i=1}^{n}{(n+i)\binom{2n}{n-i}}-\sum_{i=1}^{n-1}{(n-i)\binom{2n}{n-i}} \\ & =\sum_{i=1}^{n}{2n\binom{2n-1}{n-i}}-\sum_{i=1}^{n-1}{2n\binom{2n-1}{n-i-1}} \\ & =\sum_{i=0}^{n-1}{2n\binom{2n-1}{i}}-\sum_{i=0}^{n-2}{2n\binom{2n-1}{i}} \\ & =2n\binom{2n-1}{n-1} \\ & =n \binom{2n}{n} \end{align}

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.