1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
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 problem

  1. Jan 31, 2010 #1
    1. The problem statement, all variables and given/known data

    [tex]{n \choose 0} + {n+1 \choose 1} + {n+2 \choose 2}+...+{n+r \choose r} = {n+r+1 \choose r}[/tex]

    We have to prove by counting both sides in a different way.

    For example, consider [tex]{n \choose 0}^2 + {n \choose 1}^2+...+{n \choose n}^2 = {2n \choose n}[/tex]
    The RHS can be described as a way to choose a committee of size n from n women and n men.
    Then, the LHS is the number of ways to choose a committee of size n with 0 women and n men + number of ways to choose 1 woman and n-1 men, etc.


    3. The attempt at a solution
    The confusing part for me on this problem is that the amount you choose from doesn't stay the same. I'm having trouble thinking of a scenario where the pool you choose from increases as you choose more.

    One observation I've made is that (for the LHS) the amount you DON'T choose is always the same, n.
     
  2. jcsd
  3. Jan 31, 2010 #2

    tiny-tim

    User Avatar
    Science Advisor
    Homework Helper

    Hi davemoosehead! :smile:

    The RHS is the number of ways of choosing n+1 from n+r+1, and as you say the LHS is different numbers of ways of choosing n …

    so where does the extra one come in? :wink:
     
  4. Jan 31, 2010 #3
    I've been thinking about this all afternoon, and still cannot come up with anything. It's given me a new way of looking at it though which makes it look less intimidating.

    So you're saying think of it in terms of what we're not choosing (n+1), rather than what we are choosing (r). So..
    [tex]
    {n \choose n} + {n+1 \choose n} + {n+2 \choose n}+...+{n+r \choose n} = {n+r+1 \choose n+1}
    [/tex]
    would this be equivalent?
     
  5. Jan 31, 2010 #4

    tiny-tim

    User Avatar
    Science Advisor
    Homework Helper

    Yes …

    and now concentrate on where the first one (of n+1) is. :wink:
     
  6. Jan 31, 2010 #5
    If we lined up all the n+r+1 things, the first one of [tex]{n+1 \choose n}[/tex] would be the one after the last one of [tex]{n+1 \choose 1}[/tex]
     
  7. Feb 1, 2010 #6

    tiny-tim

    User Avatar
    Science Advisor
    Homework Helper

    uhh? :confused:

    No, I meant eg how many selections are there (of n+1 from n+r+1) in which the first one selected is number 7 (ie the previous 6 are not selected)? :smile:
     
  8. Feb 3, 2010 #7
    If the first 6 are not selected, then you would have (n+r+1-6 C n+1) ?

    I'm having a hard time following what you are saying.
     
  9. Feb 3, 2010 #8

    tiny-tim

    User Avatar
    Science Advisor
    Homework Helper

    Yes, but if the first one selected is number 7 (ie the previous 6 are not selected)?
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook