Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
3  
You can point to the previous question you posted so that others can see the motivation for this question. –  user17762 Jun 5 '11 at 5:09

3 Answers 3

up vote 4 down vote accepted

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

share|improve this answer
    
@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? –  kuch nahi Jun 6 '11 at 17:55
    
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. –  kuch nahi Jun 6 '11 at 18:01
    
@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 –  user17762 Jun 6 '11 at 19:12
    
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$) –  kuch nahi Jun 6 '11 at 19:30
    
@yayu: Nope only the odd terms contribute $2k$ –  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) $$

share|improve this answer
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. –  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}$$

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

share|improve this answer
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. –  kuch nahi Jun 5 '11 at 5:49

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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