4
$\begingroup$

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
    You can point to the previous question you posted so that others can see the motivation for this question.2011-06-05

3 Answers 3

4

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}$)

  • 0
    I see now. This was a really good answer. (Even better than the last one)2011-06-06
1

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
    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.2011-06-05
0

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}$

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

  • 2
    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.2011-06-05