How to evaluate the expression $$\displaystyle \sum_{k=1}^n \binom{2k}{2}$$ using a combinatorial argument?

Sorry I have little clue so cannot provide any working for it. Not homework. Related to previous question.

  • 3
    $\begingroup$ You can point to the previous question you posted so that others can see the motivation for this question. $\endgroup$ – user17762 Jun 5 '11 at 5:09

A simple combinatorial argument of choosing $2$ balls from $2k$ red balls and $1$ blue ball gives us $$\binom{2k+1}{2} = \binom{2k}{2} + 2k$$ And $$\sum_{k=1}^{2n+1} \binom{k}{2} = \binom{2n+2}{3}$$ Hence $$2 \sum_{k=1}^{n} \binom{2k}{2} + \sum_{k=1}^{n} 2k = \binom{2n+2}{3}$$ and hence $$2 \sum_{k=1}^{n} \binom{2k}{2} = \binom{2n+2}{3} - \sum_{k=1}^{n} 2k$$ $$\sum_{k=1}^{n} \binom{2k}{2} = \frac{\binom{2n+2}{3}}{2} - \binom{n+1}{2}$$

(Some of the machinery for this argument has been borrowed from this question in particular the $\displaystyle \sum_{k=1}^{n} \binom{k}{2} = \binom{n+1}{3}$)

  • $\begingroup$ @Sivaram, I am confused here. What is the relationship between $\sum_{k=1}^n \binom{2k+1}{2}$ and $\sum_{k=1}^{2n+1}\binom{k}{2}$ that you have used? $\endgroup$ – kuch nahi Jun 6 '11 at 17:55
  • $\begingroup$ I suspect it is $$\sum_{k=1}^n \binom{2k+1}{2} =\frac{1}{2} \sum_{k=1}^{2n+1}\binom{k}{2}$$ from a bijection on $$ \binom{n+1}{r+1} = \binom{n}{r}+\binom{n-1}{r}+\cdots + \binom{r}{r}$$ ?Then an additional factor of 2 would be needed in the second summand of the third equation. Thanks a lot for any clarifications. $\endgroup$ – kuch nahi Jun 6 '11 at 18:01
  • $\begingroup$ @yayu: Split the $\sum_{k=1}^{2n+1} \binom{k}{2}$ into odd and even parts and use that $\binom{2k+1}{2} = \binom{2k}{2} + 2k$ for the odd parts $\endgroup$ – user17762 Jun 6 '11 at 19:12
  • $\begingroup$ Yes, that is what I had reasoned and tried to say in the second comment. So there should be an additional factor of two (i.e second summation in third equation should be $\sum 4k$ instead of $\sum 2k$) $\endgroup$ – kuch nahi Jun 6 '11 at 19:30
  • $\begingroup$ @yayu: Nope only the odd terms contribute $2k$ $\endgroup$ – user17762 Jun 6 '11 at 19:31

Well, $\binom{2k}{2} = k(2k-1) = 2k^{2} - k$. So,

$$ \sum_{k=1}^{n} \binom{2k}{2} = 2\sum_{k=1}^{n} k^{2} - \sum_{k=1}^{n} k = n(n+1) \Big( \frac{2n+1}{3} - \frac{1}{2} \Big) $$

  • 3
    $\begingroup$ yayu is looking for a combinatorial argument. (Though he did not state it in the question explicitly) I have now edited the question to emphasis that he is looking for a combinatorial argument. $\endgroup$ – user17762 Jun 5 '11 at 5:23

The magical question:

$$\displaystyle \sum_{k=1}^n \binom{2k}{2}$$

Substitute with the formula:

$$\displaystyle \sum_{k=1}^n \frac{(2k)!}{(2k-2)!2!}$$

Simplify (we can do this because we know for sure that $2k > 1$):

$$\displaystyle \sum_{k=1}^n \frac{(2k)(2k-1)}{2} = 2\sum_{k=1}^n k^2 - \sum_{k=1}^n k$$

And now:

$$2(\frac{n(n+1)(2n+1)}{6}) - \frac{n(n+1)}{2}$$


  • 2
    $\begingroup$ Thanks for answering, but it presupposes what is to be proved in the context of the previous question. Sivaram has kindly edited my question to reflect that. $\endgroup$ – kuch nahi Jun 5 '11 at 5:49

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.