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: Combinatorial Proofs of Binomial Identities

  1. Mar 1, 2010 #1

    silvermane

    User Avatar
    Gold Member

    1. The problem statement, all variables and given/known data
    (Give a combinatorial proof of each of the following identities. In other words, describe a collection of combinatorial objects and then explain two different methods for counting those objects. Leave each identity in the form given. Do not rearrange terms or use any other identity to simplify the equation.)

    Prove that for n greater than or equal to 3,
    n^3 - n = 6(nC3) + 6(nC2)


    3. The attempt at a solution
    This is my first Combinatorics class, and I must say that I don't think like this at all. It's all new to me and I don't understand anything in a combinatorial sense, but rather I understand things inductively and algebraically. Please give me a hint in how I could do this. I don't exactly want an answer, just a little help. Thank you so much for your time.
     
  2. jcsd
  3. Mar 1, 2010 #2
    Try writing n^3 - n as (n+1)*n*(n-1).

    Do you know something that this product counts?
     
  4. Mar 1, 2010 #3

    silvermane

    User Avatar
    Gold Member

    Yeah, say we have a group of n+1 people and we want to have 3 of them sit down in 3 chairs. We could seat the first person in N+1 ways.
    The second person in N ways.
    The third in N - 1 ways.
    (I write it as this because this is how the prof wants it in our hmwk)


    I think I understand how to count the left side of the equation. The right side is kinda throwing me off a little here, but I think I simplified it correctly.

    Say we arrange the right side as 3x2x(nC3)+3x2x(nC2) and look at it this way for the proof.
    Lemme know if I'm on the right track. You've been very helpful :)
     
  5. Mar 1, 2010 #4
    Yeah, that should help.

    Do you know how to interpret addition combinatorially? (If so, you probably have an idea of what to do next)
     
  6. Mar 1, 2010 #5

    silvermane

    User Avatar
    Gold Member

    Uh, that's where I am stuck. We just learned summation notation, and he just gave us this. We know that you can take separate cases and add them, but I don't know how to put it into my example. (sorry for being a burden) =/
     
  7. Mar 1, 2010 #6
    Actually, that's all I meant. If you're adding two numbers together, you're just considering two separate cases.

    Think about why (n+1) isn't explicitly appearing on the right-hand side. It'll help you figure out what two cases will work.
     
  8. Mar 1, 2010 #7

    silvermane

    User Avatar
    Gold Member

    Okay, that helps out a lot. Thank you! =)
     
  9. Mar 2, 2010 #8

    silvermane

    User Avatar
    Gold Member

    I Understand it in terms of Pascal's triangle and used an example with giving people medals. The only problem is that when I discussed the problem with the professor, I found that we are not allowed to alter the equation in any way.

    I have to explain it as a difference rule on the left side, n^3 - n
    and it must be 6(nC3) + 6(nC2) for the right side.

    I know how to explain the right side, but I am having some trouble with the left side and using the difference rule. I know that n^3 is the number of ways to distribute the medals to the people before the race, where the case of one person getting all three medals is included. I don't know why I would subtract by n though. Any ideas?
     
  10. Mar 2, 2010 #9
    All right. I don't think you'd be able to use pascal's triangle, but I don't think my instructors had a problem with factoring...

    What if we don't allow the case of one person getting all three medals? How many ways have we removed when we disallow this?
     
  11. Mar 2, 2010 #10

    silvermane

    User Avatar
    Gold Member

    Yeah, I did just what you said before reading this! It turns out that it works that way just fine. Thanks for your help :)
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook