Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Combinatorics-binomial coefficients

  1. Jun 13, 2010 #1
    1. The problem statement, all variables and given/known data

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

    2. Relevant Equations

    I think I need to use [tex]m^{3} = a*nCr(m,3)+b*nCr(m,2)+c*nCr(m,1)[/tex] and [tex]nCr(n+1,k+1)=nCr(0,k)+nCr(1,k)+...+nCr(n-1,k)+nCr(n,k)[/tex] 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 [tex]m^2=a*nCr(m,2)+b*nCr(m,1)[/tex] then a=2 and b=1 but I am not sure why, I just know it works.
     
  2. jcsd
  3. Jun 13, 2010 #2

    CompuChip

    User Avatar
    Science Advisor
    Homework Helper

    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.
     
  4. Jun 13, 2010 #3
    can you show me how you got nCr(m,3) is proportional to m(m-1)(m-2)? Obviously [tex]nCr(m,3)=\frac{m!}{3!(m-3)!}[/tex] but not sure where to go from there?
     
  5. Jun 13, 2010 #4
    How can you simplify m!/(m-3)!?
     
  6. Jun 13, 2010 #5
    Ok so that would equal [tex]\frac{1*2*3*...*(m-3)(m-2)(m-1)(m)}{1*2*3*...*(m-3)}[/tex] 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 [tex]\frac{m!}{3!(m-3)!}[/tex]?
     
  7. Jun 13, 2010 #6

    vela

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Education Advisor

    The 3! is still there, so now you have

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

    Just keep going and see where it leads you.
     
  8. Jun 13, 2010 #7
    Ok, so I did that approach on a b and c and got the following:

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

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

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

    where would I go from there though? I have three unknowns so don't I need three equations to solve for them?
     
  9. Jun 13, 2010 #8

    vela

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Education Advisor

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

    [tex]m^2 = \textrm{R} m^2 + \textrm{S} m + \textrm{T}[/tex]

    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.
     
  10. Jun 13, 2010 #9
    Alright so after doing the algebra I get a=6,b=6, and c=1. Which gives me

    [tex]m^3=6nCr(m,3)+6nCr(m,2)+nCr(m,1)[/tex].

    Then how would I sum the series [tex]1^3+2^3+3^3+...+n^3[/tex] using this?
     
  11. Jun 13, 2010 #10

    vela

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Education Advisor

    You could write

    [tex]\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][/tex]

    and use the relation you noted in your original post

    [tex]\sum_{m=0}^n \begin{pmatrix}m\\k\end{pmatrix} = \begin{pmatrix}n+1\\k+1\end{pmatrix}[/tex]

    to evaluate the sums on the RHS.
     
  12. Jun 13, 2010 #11
    Ok, so if I sum the series

    [tex]1^3+2^3+...+n^3[/tex]

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

    [tex]1^3+1, 2^3+1,....[/tex]?
     
  13. Jun 13, 2010 #12

    vela

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Education Advisor

    No. Your k values are right, but not the values for n.
     
    Last edited: Jun 13, 2010
  14. Jun 13, 2010 #13
    I think I would get

    [tex]
    \sum_{m=0}^nm^3=0+1+8+27+...+n^3
    [/tex]
     
  15. Jun 13, 2010 #14

    vela

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Education Advisor

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

    In the relation

    [tex]\sum_{m=0}^n \begin{pmatrix}m\\k\end{pmatrix} = \begin{pmatrix}n+1\\k+1\end{pmatrix}[/tex]

    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

    [tex]\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][/tex]

    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.
     
  16. Jun 13, 2010 #15
    Ok that makes sense, but how would I identify what should be on top of the summation sign? Is that from this:

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

    [/tex]
     
  17. Jun 13, 2010 #16

    vela

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Education Advisor

    You just look. What's there?
     
  18. Jun 13, 2010 #17
    Well since it's just an n up there then would this come out to be

    [tex]
    \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]
    [/tex]
     
  19. Jun 13, 2010 #18

    vela

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Education Advisor

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

    [tex]\sum_{m=0}^n \begin{pmatrix}m\\k\end{pmatrix}[/tex]

    with just one binomial coefficient,

    [tex]\begin{pmatrix}n+1\\k+1\end{pmatrix}[/tex]
     
  20. Jun 13, 2010 #19
    Ok so the answer is just

    [tex]

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

    [/tex]

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

    [tex]

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

    [/tex]
     
  21. Jun 14, 2010 #20

    vela

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Education Advisor

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

    [tex]\sum_i (A_i+B_i) = \sum_i A_i +\sum_i B_i[/tex]

    [tex]\sum_i cA_i = c \sum_i A_i[/tex]
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook