# Combinatorics-binomial coefficients

1. Jun 13, 2010

### pupeye11

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

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

2. Relevant 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

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

2. Jun 13, 2010

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

3. Jun 13, 2010

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

4. Jun 13, 2010

### Tedjn

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

5. Jun 13, 2010

### 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)!}$$?

6. Jun 13, 2010

### vela

Staff Emeritus
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.

7. Jun 13, 2010

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

8. Jun 13, 2010

### vela

Staff Emeritus
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 m2, m1, and m0 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.

9. Jun 13, 2010

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

10. Jun 13, 2010

### vela

Staff Emeritus
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.

11. Jun 13, 2010

### 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,....$$?

12. Jun 13, 2010

### vela

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

Last edited: Jun 13, 2010
13. Jun 13, 2010

### pupeye11

I think I would get

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

14. Jun 13, 2010

### vela

Staff Emeritus
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.

15. Jun 13, 2010

### pupeye11

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

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

16. Jun 13, 2010

### vela

Staff Emeritus
You just look. What's there?

17. Jun 13, 2010

### pupeye11

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

$$\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]$$

18. Jun 13, 2010

### vela

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

19. Jun 13, 2010

### pupeye11

Ok so the answer is just

$$\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]$$

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

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

20. Jun 14, 2010

### vela

Staff Emeritus
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$$