# Combinatorics - Sum of series

1. Oct 12, 2010

### tarheelborn

1. The problem statement, all variables and given/known data

Sum the series $$1^2+2^2+\cdots|n^2$$ by observing that $$m^2=2* \dbinom{m}{2} + \dbinom{m}{1}$$ and using the identity $$\dbinom{0}{k}+ \dbinom{1}{k} + \cdots+ \dbinom{m}{k}= \dbinom{m+1}{k+1}$$.

2. Relevant equations

3. The attempt at a solution

I know that $$1^2+2^2+\cdots+m^2= 2* \dbinom{1}{2}+ \dbinom{1}{1} + 2* \dbinom{2}{2}+ \dbinom{2}{1} + 2* \dbinom{3}{2} + \dbinom{3}{1} + \cdots + 2* \dbinom{m}{2} + \dbinom{m}{1}$$ but I am not picking up on how to simply this into the sum of the whole series.

2. Oct 12, 2010

### vela

Staff Emeritus
Try collecting terms so you have 2*(stuff) + (everything else).

3. Oct 12, 2010

### tarheelborn

Re: Combinatorics - Sum of series ii

OK, that gives me $$2(\dbinom{1}{2}+\dbinom{2}{2}+...+\dbinom{n}{2})+(1+2+...+n)$$ , but I'm still not seeing it.

4. Oct 12, 2010

### tarheelborn

OK, wait... The above equals $$2(\dbinom{1}{2}+ \dbinom{2}{2} +...+ \dbinom{n}{2})+(n(n+1))/2$$, so that lets me eliminate the 2's. Now I need to be able to combine the other two parts. Right?

5. Oct 12, 2010

### tarheelborn

And $$\dbinom{n}{n}=\frac{1}{6}(n-2)(n-1)n = \frac{1}{6}(n^5-2n^4-n^3+2n^2)$$. I don't know quite what I was expecting but that isn't it.

6. Oct 12, 2010

### tarheelborn

And $$\dbinom{n}{n}=\frac{1}{6}(n-2)(n-1)n = \frac{1}{6}(n^5-2n^4-n^3+2n^2)$$ is what I meant to say.

7. Oct 12, 2010

### vela

Staff Emeritus
Did you use the identity you were given?

8. Oct 12, 2010

### vela

Staff Emeritus
I don't see where you got this from. It can't be right because C(n,n)=1.

9. Oct 12, 2010

### tarheelborn

No. Hmmm... So I would have $$\frac{(n-2)(n-1)n}{6}+ \dbinom{m+1}{k+1}$$. And that equals $$\dbinom{m}{3}+ \dbinom{m+1}{k+1}$$.

10. Oct 12, 2010

### vela

Staff Emeritus
What are m and k equal to? Where did the (n-2)(n-1)n/6 come from? Where did n(n+1)/2 go to?

11. Oct 13, 2010

### tarheelborn

(n-2)(n-1)n/6 is the same as n falling power 3/3!, right? So that =$$\dbinom{m}{3}$$ So that would equal $$\dbinom{n}{3}+\dbinom{n+1}{k+1}$$. Sorry, I mixed my m's and n's.

12. Oct 13, 2010

### vela

Staff Emeritus
This is what I'm getting from what you wrote:

$$\frac{(n-2)(n-1)n}{6} = \dbinom{n}{3} = \dbinom{m}{3} = \dbinom{n}{3}+\dbinom{n+1}{k+1}$$

You have an expression in terms of n and then you're saying it's equal to something in terms of m. Where did the m come from? Then you get another expression and yet another variable appears. Where did k come from? And how is this related to the original problem?

13. Oct 13, 2010

### tarheelborn

Good grief... I am so sorry. This should read $$\frac{(n-2)(n-1)n}{6}= \dbinom{n}{3}+ \dbinom{n+1}{k+1}$$. The k comes from the identity stated in the original problem.

14. Oct 13, 2010

### vela

Staff Emeritus
Let's go back to posts #3 and #4. You had

\begin{align*} 1^2+2^2+\cdots+n^2 &= 2\left[\dbinom{1}{2}+ \dbinom{2}{2} +...+ \dbinom{n}{2}\right]+(1+2+\cdots+n) \\ &= 2\left[\dbinom{1}{2}+ \dbinom{2}{2} +...+ \dbinom{n}{2}\right]+\frac{n(n+1)}{2} \end{align*}

So far, so good. Now if you compare what's in the square brackets with the identity

$$\dbinom{0}{k}+ \dbinom{1}{k} + \cdots + \dbinom{m}{k} = \dbinom{m+1}{k+1}$$

they look very similar. The first term of the lefthand side of the identity is always equal to 0, so it doesn't really matter if it's there or not. If you drop it, what's left and what's in the square brackets will match exactly if you choose the right values of m and k. What should m and k equal, possibly in terms of n?

15. Oct 13, 2010

### tarheelborn

Yes, they do look very similar. I understand that I can eliminate the first term with no consequences. So... It seems that k has to be 2. I don't know how to say that in terms of n. m, on the other hand, would be n-1, wouldn't it?

16. Oct 13, 2010

### vela

Staff Emeritus
k is indeed equal to 2. To see what m equals, look at the very last terms. In order for them to match exactly, you need m=n.

17. Oct 13, 2010

### tarheelborn

So, in fact, I end up with $$\dbinom{n+1}{2} + \frac{n(n+1)}{2}$$?

18. Oct 13, 2010

### vela

Staff Emeritus
Almost. Since k=2, you should have

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

19. Oct 14, 2010

### tarheelborn

Thank you so much for sticking this out with me! I have learned SO much from these posts; it's not just an answer to me. Thank you.