Combinatorics-binomial coefficients

[pupeye11]

Homework Statement

Find integers a,b, and c such that m^{3} = a*nCr(m,3)+b*nCr(m,2)+c*nCr(m,1) for all m. Then sum the series 1^3+2^3+3^3+...+n^3

Homework Equations

I think I need to use m^{3} = a*nCr(m,3)+b*nCr(m,2)+c*nCr(m,1) and nCr(n+1,k+1)=nCr(0,k)+nCr(1,k)+...+nCr(n-1,k)+nCr(n,k) to be able to sum the series but I am not sure

The Attempt at a Solution

I am not really sure how to get started, I originally thought that a=3, b=2, and c=1 but the more I think about it that doesn't seem right. I believe that if it was just m^2=a*nCr(m,2)+b*nCr(m,1) then a=2 and b=1 but I am not sure why, I just know it works.

 

[CompuChip]

I would start by writing out the combinations.
For example, nCr(m, 3) is proportional to m(m-1)(m-2).
Then you will get a polynomial equation in m, which should hold for any m, therefore you can equate the coefficients of the different degrees.

 

[pupeye11]

can you show me how you got nCr(m,3) is proportional to m(m-1)(m-2)? Obviously nCr(m,3)=\frac{m!}{3!(m-3)!} but not sure where to go from there?

 

[Tedjn]

How can you simplify m!/(m-3)!?

 

[pupeye11]

Ok so that would equal \frac{1*2*3*...*(m-3)(m-2)(m-1)(m)}{1*2*3*...*(m-3)} so obviously everything up to (m-3) will cancel out and I am left with m(m-1)(m-2) but what happens to the 3 in the denominator of \frac{m!}{3!(m-3)!}?

 

[vela]

The 3! is still there, so now you have

m^3 = a\left[\frac{m(m-1)(m-2)}{3!}\right]+b*\textrm{nCr}(m,2)+c*\textrm{nCr}(m,1)

Just keep going and see where it leads you.

 

[pupeye11]

Ok, so I did that approach on a b and c and got the following:

m^3=a[\frac{m(m-1)(m-2)}{3!}]+b[\frac{m(m-1)}{2!}]+cm

which if I factor out a m and divide by it I'll get

m^2=a[\frac{(m-1)(m-2)}{3!}]+b[\frac{(m-1)}{2!}]+c

where would I go from there though? I have three unknowns so don't I need three equations to solve for them?

 

[vela]

Now you multiply out the RHS and collect terms. When you do that, you'll have

m^2 = \textrm{R} m^2 + \textrm{S} m + \textrm{T}

where R, S, and T are some combination of a, b, and c. (I'm leaving that for you to work out.) For this equation to hold, the coefficients of m², m¹, and m⁰ on the LHS and RHS have to match, so you need to have 1=R, 0=S, and 0=T. These are the three equations that will let you solve for the three unknowns a, b, and c.

 

[pupeye11]

Alright so after doing the algebra I get a=6,b=6, and c=1. Which gives me

m^3=6nCr(m,3)+6nCr(m,2)+nCr(m,1).

Then how would I sum the series 1^3+2^3+3^3+...+n^3 using this?

 

[vela]

You could write

\sum_{m=0}^n m^3 = \sum_{m=0}^n \left[ 6\begin{pmatrix}m\\3\end{pmatrix}+6\begin{pmatrix}m\\2\end{pmatrix}+\begin{pmatrix}m\\1\end{pmatrix}\right]

and use the relation you noted in your original post

\sum_{m=0}^n \begin{pmatrix}m\\k\end{pmatrix} = \begin{pmatrix}n+1\\k+1\end{pmatrix}

to evaluate the sums on the RHS.

 

[pupeye11]

Ok, so if I sum the series

1^3+2^3+...+n^3

using this then the 3, 2, or 1 would be the k values while the n values for each would be

1^3+1, 2^3+1,...?

 

[vela]

No. Your k values are right, but not the values for n.

 

[pupeye11]

I think I would get

<br /> \sum_{m=0}^nm^3=0+1+8+27+...+n^3<br />

 

[vela]

That's right. Sorry, I realized you were getting confused about the RHS and edited my earlier post.

In the relation

\sum_{m=0}^n \begin{pmatrix}m\\k\end{pmatrix} = \begin{pmatrix}n+1\\k+1\end{pmatrix}

the n that appears on top of the summation is the same n that appears on the righthand side of the equation, so when you use the relation to evaluate

\sum_{m=0}^n \left[ 6\begin{pmatrix}m\\3\end{pmatrix}+6\begin{pmatrix} m\\2\end{pmatrix}+\begin{pmatrix}m\\1\end{pmatrix} \right]

you want to take whatever is on top of the summation and use that same expression for the n when you write it in terms of the binomial coefficients.

 

[pupeye11]

Ok that makes sense, but how would I identify what should be on top of the summation sign? Is that from this:

<br /> \sum_{m=0}^nm^3=0+1+8+27+...+n^3<br /> <br />

 

[vela]

You just look. What's there?

 

[pupeye11]

Well since it's just an n up there then would this come out to be

<br /> \sum_{m=0}^n \left[ 6\begin{pmatrix}n+1\\4\end{pmatrix}+6\begin{pmatrix} n+1\\3\end{pmatrix}+\begin{pmatrix}n+1\\2\end{pmatrix} \right]<br />

 

[vela]

Close, but the summation shouldn't be there anymore. The relation tells you how to write a sum of binomial coefficients,

\sum_{m=0}^n \begin{pmatrix}m\\k\end{pmatrix}

with just one binomial coefficient,

\begin{pmatrix}n+1\\k+1\end{pmatrix}

 

[pupeye11]

Ok so the answer is just

<br /> <br /> \left[ 6\begin{pmatrix}n+1\\4\end{pmatrix}+6\begin{pmatrix} n+1\\3\end{pmatrix}+\begin{pmatrix}n+1\\2\end{pmatrix}+...+\begin{pmatrix}n+1\\k+1\end{pmatrix} \right]<br /> <br />

I am not sure that last part should be in there though... but I think it should since I am summing over

<br /> <br /> 1^3+2^3+...+n^3<br /> <br />

 

[vela]

Nope, try again. You might find these property of summations helpful:

\sum_i (A_i+B_i) = \sum_i A_i +\sum_i B_i

\sum_i cA_i = c \sum_i A_i

 

[pupeye11]

Ok so using those properties, I am able to get:

<br /> \left[ 6\begin{pmatrix}n+1\\4\end{pmatrix}+6\begin{pmatrix} n+1\\3\end{pmatrix}+\begin{pmatrix}n+1\\2\end{pmatrix}\right] =<br /> 6 \sum \begin{pmatrix}n+1\\4\end{pmatrix}+6 \sum \begin{pmatrix}n+1\\3\end{pmatrix}+\begin{pmatrix}n+1\\2\end{pmatrix}<br />

correct?

 

[pupeye11]

Does

<br /> 6 \sum \begin{pmatrix}n+1\\4\end{pmatrix} = 6\left(\frac{(n-2)(n-1)(n)(n+1)}{24}\right)<br />

<br /> 6 \sum \begin{pmatrix}n+1\\3\end{pmatrix} = 6\left(\frac{(n-1)(n)(n+1)}{6}\right)<br />

<br /> \sum \begin{pmatrix}n+1\\2\end{pmatrix} = \frac{n(n+1)}{2}<br />

 

[vela]

No, you're mixing steps up. Just take it step by step. Let's recap what you've done so far. First, you found

m^3 = 6\begin{pmatrix}m\\3\end{pmatrix}+6\begin{pmatrix} m\\2\end{pmatrix}+\begin{pmatrix}m\\1\end{pmatrix}

Next, you let m run from 0 to n and added all the results to get

\sum_{m=0}^n m^3 = \sum_{m=0}^n \left[ 6\begin{pmatrix}m\\3\end{pmatrix} + 6\begin{pmatrix}m\\2\end{pmatrix} + \begin{pmatrix}m\\1\end{pmatrix} \right]

Up to here you're fine. Now back in post 15, you noted the LHS equals

\sum_{m=0}^nm^3=0+1+8+27+...+n^3

which is the sum you're trying to find. You want to now evaluate the RHS side, so use the properties to break up the RHS. Once you've done that, then use the identity

\sum_{m=0}^n \begin{pmatrix}m\\k\end{pmatrix} = \begin{pmatrix}n+1\\k+1\end{pmatrix}

to replace each sum with the appropriate binomial coefficient. Finally, evaluate each binomial coefficient and simplify to get the final result.

 

[pupeye11]

Ok so if I start at

<br /> \sum_{m=0}^n m^3 = \sum_{m=0}^n \left[ 6\begin{pmatrix}m\\3\end{pmatrix} + 6\begin{pmatrix}m\\2\end{pmatrix} + \begin{pmatrix}m\\1\end{pmatrix} \right]<br />

then i replace the LHS with what we know that is we get

<br /> 0+1+8+27+...+n^3 = \sum_{m=0}^n \left[ 6\begin{pmatrix}m\\3\end{pmatrix} + 6\begin{pmatrix}m\\2\end{pmatrix} + \begin{pmatrix}m\\1\end{pmatrix} \right]<br />

which if I use the properties will become (looking only at the RHS now)

<br /> = 6 \sum_{m=0}^{n} \begin{pmatrix}m\\3\end{pmatrix}+6 \sum_{m=0}^{n} \begin{pmatrix}m\\2\end{pmatrix}+ \sum_{m=0}^{n} \begin{pmatrix}m\\1\end{pmatrix}<br />

which if i use the identity you posted last I will get

<br /> 6 \begin{pmatrix}n+1\\4\end{pmatrix}+6 \begin{pmatrix}n+1\\3\end{pmatrix}+ \begin{pmatrix}n+1\\2\end{pmatrix}<br />

correct?

 

[vela]

Yes, that's correct! Now you just need to evaluate those coefficients and simplify.

 

[pupeye11]

Alright, so evaluating those coefficients I will get what I got before...

<br /> 6 \begin{pmatrix}n+1\\4\end{pmatrix} = 6\left(\frac{(n-2)(n-1)(n)(n+1)}{24}\right) = \frac{(n-2)(n-1)(n)(n+1)}{4}<br />

<br /> 6 \begin{pmatrix}n+1\\3\end{pmatrix} = 6\left(\frac{(n-1)(n)(n+1)}{6}\right) = (n-1)(n)(n+1)<br />

<br /> \begin{pmatrix}n+1\\2\end{pmatrix} = \frac{n(n+1)}{2} = \frac{n(n+1)}{2}<br />

 

[vela]

I hope you realize there's a world of difference in meaning between what you wrote earlier:

<br /> 6 \sum \begin{pmatrix}n+1\\4\end{pmatrix} = 6\left(\frac{(n-2)(n-1)(n)(n+1)}{24}\right)<br />

<br /> 6 \sum \begin{pmatrix}n+1\\3\end{pmatrix} = 6\left(\frac{(n-1)(n)(n+1)}{6}\right)<br />

<br /> \sum \begin{pmatrix}n+1\\2\end{pmatrix} = \frac{n(n+1)}{2}<br />

and what you wrote just now:

<br /> 6 \begin{pmatrix}n+1\\4\end{pmatrix} = 6\left(\frac{(n-2)(n-1)(n)(n+1)}{24}\right) = \frac{(n-2)(n-1)(n)(n+1)}{4}<br />

<br /> 6 \begin{pmatrix}n+1\\3\end{pmatrix} = 6\left(\frac{(n-1)(n)(n+1)}{6}\right) = (n-1)(n)(n+1)<br />

<br /> \begin{pmatrix}n+1\\2\end{pmatrix} = \frac{n(n+1)}{2} = \frac{n(n+1)}{2}<br />

 

[pupeye11]

Well yeah, I just meant what I wrote earlier on the right hand side. Sorry for not clarifying. To get the simplest form possible though I should multiply those out and then add like terms correct? Or is this form considered more simple?

 

[vela]

OK, I just wanted to make sure you didn't have that misconception.

You should combine the terms. The answer simplifies quite a bit.

 

[pupeye11]

Alright, thanks for all your help once again! I'm sure I'll have more questions on here later tonight or during this week if you aren't sick of helping me yet. Thanks again!