Results 1 to 3 of 3

Math Help - Combinatorics Proof?

  1. #1
    Junior Member
    Joined
    Sep 2009
    Posts
    37

    Combinatorics Proof?

    For positive integers n, r show that:

    C(n+r+1,r) = C(n+r,r) + C(n+r-1,r-1) + ... + C(n+2,2) + C(n+1,1) + C(n,0)

    = C(n+r,n) + C(n+r-1,n) + ... + C(n+2,n) + C(n+1,n) + C(n,n)


    Now, I've tried expanding the combinations, and I was able to get (n!) in the denominator of every term, though I'm not sure if that is even relevant to the proof. Not far, I know, but essentially, I'm stuck there and I don't know where to go.


    Thanks in advance for any and all help.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Grandad's Avatar
    Joined
    Dec 2008
    From
    South Coast of England
    Posts
    2,570
    Thanks
    1
    Hello Tulki
    Quote Originally Posted by Tulki View Post
    For positive integers n, r show that:

    C(n+r+1,r) = C(n+r,r) + C(n+r-1,r-1) + ... + C(n+2,2) + C(n+1,1) + C(n,0)

    = C(n+r,n) + C(n+r-1,n) + ... + C(n+2,n) + C(n+1,n) + C(n,n)


    Now, I've tried expanding the combinations, and I was able to get (n!) in the denominator of every term, though I'm not sure if that is even relevant to the proof. Not far, I know, but essentially, I'm stuck there and I don't know where to go.


    Thanks in advance for any and all help.
    We do the first part by Induction. The second is immediately obvious. I'm using the notation \binom{n}{r} to denote {^nC_r}.

    First we prove the Lemma: \binom{n+r+1}{r+1}+\binom{n+r+1}{r}= \binom{n+r+2}{r+1}

    Proof of Lemma:

    \binom{n+r+1}{r+1}+\binom{n+r+1}{r}= \frac{(n+r+1)!}{(r+1)!n!}+ \frac{(n+r+1)!}{r!(n+1)!}

    = \frac{(n+r+1)!(n+1)}{(r+1)!(n+1)!}+ \frac{(n+r+1)!(r+1)}{(r+1)!(n+1)!}, using the fact that (n+1)! = n!(n+1) and (r+1)!=r!(r+1)

    =\frac{(n+r+1)!([n+1]+[r+1])}{(r+1)!(n+1)!}

    =\frac{(n+r+2)!}{(r+1)!(n+1)!}

    = \binom{n+r+2}{r+1}

    Then the Induction Hypothesis: Suppose P(r) is the propositional function: For any n,\, \binom{n+r+1}{r}=\binom{n+r}{r}+\binom{n+r-1}{r-1}+...+\binom{n+2}{2}+\binom{n+1}{1}+\binom{n}{0}

    Then, using the above Lemma:

    P(r) \Rightarrow \binom{n+[r+1]+1}{r+1}=\binom{n+r+1}{r+1}+\binom{n+r+1}{r}

    =\binom{n+r+1}{r+1}+\binom{n+r}{r}+\binom{n+r-1}{r-1}+...+\binom{n+2}{2}+\binom{n+1}{1}+\binom{n}{0}

    So P(r) \Rightarrow P(r+1).

    Now P(0) is self-evident.

    So the result is proved, by Induction, for all r \ge 0

    For the second part, we note that for all i,\, \binom{n+r-i}{r-i}=\binom{n+r-i}{n}, and the result follows immediately.

    Grandad
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Sep 2009
    Posts
    37
    Wow. Ha, we haven't even started with Induction yet, but in any case, thank you very much.

    I'll study your response until I totally understand it!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Combinatorics proof help
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: February 3rd 2010, 07:09 AM
  2. Combinatorics & Partitions proof
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: November 22nd 2009, 07:04 AM
  3. Combinatorics
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: September 30th 2009, 02:07 PM
  4. Perfect Square combinatorics proof
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: September 27th 2009, 01:43 AM
  5. Combinatorics Proof
    Posted in the Statistics Forum
    Replies: 1
    Last Post: March 27th 2007, 10:36 AM

Search Tags


/mathhelpforum @mathhelpforum