Summing Series Using Combinatorial Identities

[tarheelborn]

Homework Statement

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

Homework Equations

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.

 

[vela]

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

 

[tarheelborn]

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

 

[tarheelborn]

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

 

[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.

 

[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.

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.

 

[vela]

Did you use the identity you were given?

 

[vela]

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.

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

 

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

 

[vela]

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?

 

[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.

 

[vela]

(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.

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?

 

[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.

 

[vela]

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

$$\begin{align*}<br /> 1^2+2^2+\cdots+n^2 &= 2\left[\dbinom{1}{2}+ \dbinom{2}{2} +...+ \dbinom{n}{2}\right]+(1+2+\cdots+n) \\<br /> &= 2\left[\dbinom{1}{2}+ \dbinom{2}{2} +...+ \dbinom{n}{2}\right]+\frac{n(n+1)}{2}<br /> \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?

 

[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?

 

[vela]

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.

 

[tarheelborn]

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

 

[vela]

Almost. Since k=2, you should have

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

 

[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.