Results 1 to 3 of 3

Math Help - How to give combinatorial proofs

  1. #1
    Junior Member
    Joined
    Nov 2009
    Posts
    38

    How to give combinatorial proofs

    I'm trying to make a combotorial proof of this:

    {2 \choose 2} + {3 \choose 2} + {4 \choose 2} + ... + {n-1 \choose 2} = {n \choose 3}

    I've proved this using algebra and induction pretty easily. It was just basically expanding it out and cancelling terms. However, I have no idea how to give a combinatorial proof. I've looked at examples in my text book and they all seem to vary and there's no clear way of how to approach a combotorial proof.

    Can anyone help get me started?

    Thanks!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Newbie
    Joined
    Jan 2008
    Posts
    19
    Trivial for n=3.

    n \choose 3 is the number of ways to choose subsets of size 3 from a set of size n.

    Fix X of cardinality n. Then, for x\in X there are two cases.

    Case 1: Count number of subsets containing x. There are n-1\choose  2

    Case 2: Count the number of subsets not containing x. There are n-1\choose 3

    By induction, {n-1\choose 3}={2 \choose 2} + \cdots + {n-2 \choose 2}

    Result follows.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Nov 2009
    Posts
    38
    I actually figured this out by staring at it for 3 hours straight. Can't use induction

    Anyways, I said that ch(n, 3) is the subset of all three element subsets, which can be divided into further subsets containing highest element n-1, n-2, ... , 3, and each of those subsets you would have to choose 2 more elements that are less than the highest element of that subset. This would give you ch(n-1, 2), ch(n-2, 2), ... , ch(2, 2) since the last subset you would only have a pool of 2 to choose from.

    Seems to make sense in my crazy head
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Give a combinatorial proof
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: February 3rd 2011, 02:41 AM
  2. Replies: 7
    Last Post: October 28th 2010, 08:40 AM
  3. Combinatorial Proofs
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: March 15th 2010, 10:05 AM
  4. Can't do combinatorial proofs. Can someone help?
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 20th 2009, 09:39 AM
  5. Replies: 3
    Last Post: October 6th 2007, 02:01 PM

Search Tags


/mathhelpforum @mathhelpforum