Results 1 to 3 of 3

Math Help - Combinatorial proof of a binomial identity

  1. #1
    Junior Member gusztav's Avatar
    Joined
    Jan 2008
    Posts
    46
    Awards
    1

    Combinatorial proof of a binomial identity

    Hi, I'm trying to combinatorially prove the following identity:

    \sum_{i=0}^{r} \binom{n+i}{n}=\binom{n+1+r}{n+1}

    On the right side, \binom{n+1+r}{n+1} is the number of ways we can choose a (n+1)-element subset from a (n+1+r)-element set, while on the left side there is the sum of ways we can select an n-element subset from a n-element, (n+1)-element,..., (n+r)-element set...

    How can we prove that the numbers on both sides of the equation are actually identical?

    I'd be really grateful for any help.

    Thanks!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member PaulRS's Avatar
    Joined
    Oct 2007
    Posts
    571
    See here
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Aug 2008
    Posts
    3
    You could try using proof by induction:
    You need this formula,  \binom{n}{j}=\frac{n!}{j!\left(n-j\right)!}

    1: let r=1 and show that the two sides are equal.

    2: Assume that it's true for r = k.

    This tells us, \sum_{i=0}^{k}\binom{n+i}{n}=\binom{n+k+1}{n+1}

    3: Now prove that it's true for r = k+1
    \sum_{i=0}^{k+1}\binom{n+i}{n}=\sum_{i=0}^{k}\bino  m{n+i}{n}+\binom{n+k+1}{n}

    This is equal to, \binom{n+k+1}{n+1}+\binom{n+k+1}{n}=\binom{n+k+2}{  n+1}

    Now making use of the formula from the start

    \frac{\left(n+k+1\right)!}{\left(n+1\right)!\left(  k\right)!} +\frac{\left(n+k+1\right)!}{n!\left(k+1\right)!} = \frac{\left(n+k+2\right)!}{\left(n+1\right)!\left(  k+1\right)!}

    simplify the LHS


     \frac{\left(n+k+1\right)!n!\left(k+1\right)! +\left(n+k+1\right)!\left(n+1\right)!k!}{\left(n+1  \right)!\left(k!\right)\left(n\right)!\left(k+1\ri  ght)!}= \frac{\left(n+k+2\right)!}{\left(n+1\right)!\left(  k+1\right)!}

    using n! = n\left(n-1\right)! and simplifying further

     \frac{\left(n+k+1\right)!n!\left(k+1\right)\left(k  \right)! +\left(n+k+1\right)!\left(n+1\right)\left(n\right)  !k!}{\left(n+1\right)!\left(k!\right)\left(n\right  )!\left(k+1\right)!}= \frac{\left(n+k+2\right)\left(n+k+1\right)!}{\left  (n+1\right)!\left(k+1\right)!}

    You can show the two sides are equal for k+1 so equal for all k ( or r)
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Prove the identity using a combinatorial proof
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: April 25th 2011, 06:51 PM
  2. Combinatorial proof for an identity
    Posted in the Discrete Math Forum
    Replies: 10
    Last Post: April 23rd 2011, 04:12 PM
  3. Binomial Inequality - Combinatorial Proof?
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: January 24th 2011, 02:34 PM
  4. Combinatorial proof of derangement identity
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: July 29th 2010, 02:40 PM
  5. interesting combinatorial identity proof
    Posted in the Math Challenge Problems Forum
    Replies: 1
    Last Post: November 29th 2009, 04:34 PM

Search Tags


/mathhelpforum @mathhelpforum