Results 1 to 2 of 2

Math Help - combinations proof

  1. #1
    Gul
    Gul is offline
    Junior Member
    Joined
    Oct 2008
    From
    Brisbane
    Posts
    25

    combinations proof

    To prove a combinations equality:

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

    -> (n+2 C r+1) = (n+2)! / (n+2 - (r+1))! (r+1)!

    -> (n C r+1) = n! / (n - (r+1))! (r+1)!

    -> 2 (n C r ) = 2n! / (n - r)! r!

    -> (n C r-1) = n! / (n - (r-1))! (r-1)!


    Then I got this:

    (n+2)! / (n - r + 1)! (r+1)!

    = [n! / (n - r - 1)! (r+1)!] + [2n! / (n - r)! r!] + [n! / (n - r + 1)! (r-1)!]

    Any help from here will be greatly appreciated. can get a common denominator, but I am wondering if there is a better/quicker approach.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Junior Member
    Joined
    May 2009
    Posts
    27
    The way you're doing it will certainly work.

    Here's another way.

    We want to show that the left side counts the same number of things as the right side.

    \binom{n+2}{r+1} is the number of ways to choose a subset of size r+1 from the set \{1,2,3,\cdots,n,n+1.n+2\}.

    There are 4 cases.

    We can choose a subset that contains neither n+1 nor n+2. This can be done in \binom{n}{r+1}, as we're now choosing a size r+1 subset from the set \{1,2,\cdots,n\}.

    We can choose a subset that contains n+1 but not n+2.
    This can be done in \binom{n}{r} ways, as we are now choosing size r subsets from the set \{1,2,\cdots.n\}.

    Similarly, we can choose a subset that contains n+2 but not n+1 in \binom{n}{r} ways.

    Finally. we can choose a subset that contains both n+1 and n+2. This can be done in \binom{n}{r-1} ways.

    Add the 4 cases and we have the desired result.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Proof regarding combinations
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: February 18th 2010, 02:44 PM
  2. Proof with Combinations
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: October 20th 2009, 08:04 AM
  3. combinations proof by induction?
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: June 18th 2009, 12:03 AM
  4. [SOLVED] Discrete Math Proof: Combinations
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: February 24th 2009, 06:46 PM
  5. Combinations Proof
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: July 14th 2008, 02:09 AM

Search Tags


/mathhelpforum @mathhelpforum