Results 1 to 3 of 3

Math Help - Another combinatorial proof

  1. #1
    Member oldguynewstudent's Avatar
    Joined
    Oct 2009
    From
    St. Louis Area
    Posts
    244

    Another combinatorial proof

    Give combinatorial or bijective proofs of the following. Part of your job is to determine all values of n,k, and/or m for which the identities are valid.

    c) \left({0\atop m}\right)+\left({1\atop m}\right)+\left({2\atop m}\right)+\ldots+\left({n\atop m}\right)=\left({n+1\atop m+1}\right)

    I can't get very far with this one either. I notice that all terms on the left hand side are zero until we get to \left({m\atop m}\right). Then I calculate all terms equal 1, so we have n-m terms which makes the left hand side equal n-m.

    The right hand side I get \frac{(n+1)!}{(m+1)!(n+1-m-1)!}=\frac{(n+1)!}{n!(m+1)}=\frac{n+1}{m+1}

    I can get no further.

    Can someone help or tell me if I have the whole combinatorial proof thing wrong.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member
    Joined
    Mar 2010
    From
    Bratislava
    Posts
    116
    Thanks
    1
    Quote Originally Posted by oldguynewstudent View Post
    Give combinatorial or bijective proofs of the following. Part of your job is to determine all values of n,k, and/or m for which the identities are valid.

    c) \left({0\atop m}\right)+\left({1\atop m}\right)+\left({2\atop m}\right)+\ldots+\left({n\atop m}\right)=\left({n+1\atop m+1}\right)

    I can't get very far with this one either. I notice that all terms on the left hand side are zero until we get to \left({m\atop m}\right). Then I calculate all terms equal 1, so we have n-m terms which makes the left hand side equal n-m.

    The right hand side I get \frac{(n+1)!}{(m+1)!(n+1-m-1)!}=\frac{(n+1)!}{n!(m+1)}=\frac{n+1}{m+1}

    I can get no further.

    Can someone help or tell me if I have the whole combinatorial proof thing wrong.
    Use induction. Inductive step: Suppose that
    \binom0m+\binom1m+\dots+\binom nm=\binom{n+1}{m+1}.
    We show that the same is true for n+1.
    \binom0m+\binom1m+\dots+\binom nm+\binom{n+1}m=\binom{n+1}{m+1}+\binom{n+1}m=\bin  om{n+2}{m+1}.

    See Sum of k Choose m up to n - ProofWiki
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Jul 2010
    Posts
    9
    Remember that the point of a combinatorial proof is that they are easier to write than simply grinding out the identity, as you seem do be doing. In a combinatorial proof, you have to ask a question, and then answer it by counting it in two different ways.

    Therefore, consider this.

    Remember, the RHS basically is asking the number of ways to choose m+1 elements from a set with n+1 elements. So, you have one answer you need: \binom{n+1}{m+1}. Now on the left hand side, you have a sum. What does that imply? Or in other words, what conditions must you apply to get a sum?
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Combinatorial proof?
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: April 3rd 2011, 04:22 PM
  2. Combinatorial Proof
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: August 18th 2010, 05:08 AM
  3. Combinatorial proof
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: July 4th 2010, 09:02 PM
  4. Combinatorial proof help
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: September 30th 2009, 06:43 PM
  5. Combinatorial Proof
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: March 17th 2008, 05:40 PM

Search Tags


/mathhelpforum @mathhelpforum