Results 1 to 4 of 4

Math Help - Combinatorical proof

  1. #1
    Member
    Joined
    Sep 2009
    Posts
    177
    Thanks
    1

    Combinatorical proof

    Hey guys, I just learned about combinatorical style proofs. Anyways, I was wondering if you could just tell me if the following proof of mine is acceptable.

    Claim:  n\choose 0 +  n\choose 1 +...+ n\choose n= 2^n

    Proof. The left hand side and the right hand side count the number of subsets of an n element set. We need to show that the RHS is equilivent to the LHS. We do this as follows. Take an arbitrary subset of the n element set. We need to determine whether or not each element of the n set is in this subset. This gives us
    2x2x2x...x2=  2^n possibilities. Hence, RHS=LHS.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    2
    Quote Originally Posted by Chris11 View Post
    Hey guys, I just learned about combinatorical style proofs. Anyways, I was wondering if you could just tell me if the following proof of mine is acceptable.

    Claim:  n\choose 0 +  n\choose 1 +...+ n\choose n= 2^n

    Proof. The left hand side and the right hand side count the number of subsets of an n element set. We need to show that the RHS is equilivent to the LHS. We do this as follows. Take an arbitrary subset of the n element set. We need to determine whether or not each element of the n set is in this subset. This gives us
    2x2x2x...x2=  2^n possibilities. Hence, RHS=LHS.

    I can't see how you think the above proves anything...The easiest way to prove it is algebraically: 2^n=(1+1)^n=\sum\limits^n_{k=0}\binom{n}{k}1^k1^{n-k}

    Tonio
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member
    Joined
    Apr 2009
    Posts
    678
    Thanks
    1
    @Tonio - I think what OP was looking for is a combinatorial proof - i.e. an argument to show that LHS and RHS count the same set and hence are equal.

    @OP - You idea seems correct to me - just that you need to state is more clearly. For e.g. find out number of subsets of a set with 'n' elements. So there are two ways to do this, so on.....
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member oldguynewstudent's Avatar
    Joined
    Oct 2009
    From
    St. Louis Area
    Posts
    244
    Quote Originally Posted by Chris11 View Post
    Hey guys, I just learned about combinatorical style proofs. Anyways, I was wondering if you could just tell me if the following proof of mine is acceptable.

    Claim:  n\choose 0 +  n\choose 1 +...+ n\choose n= 2^n

    Proof. The left hand side and the right hand side count the number of subsets of an n element set. We need to show that the RHS is equilivent to the LHS. We do this as follows. Take an arbitrary subset of the n element set. We need to determine whether or not each element of the n set is in this subset. This gives us
    2x2x2x...x2=  2^n possibilities. Hence, RHS=LHS.
    How about the following:

    The left hand side counts the number of 0 element subsets of n + the number of 1 element subsets of n + ... + the number of n element subsets of n. This is the same as counting the elements of the power set of n which is known to be 2^n.

    I have had a very hard time learning combinatorial proofs. I am just now beginning to understand how to do them.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 5
    Last Post: October 19th 2010, 11:50 AM
  2. Combinatorical Identity
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: June 29th 2010, 08:39 AM
  3. combinatorical proof
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 24th 2009, 06:01 PM
  4. proof that the proof that .999_ = 1 is not a proof (version)
    Posted in the Advanced Applied Math Forum
    Replies: 4
    Last Post: April 14th 2008, 05:07 PM
  5. Beautiful combinatorical problem
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: October 28th 2007, 10:51 AM

Search Tags


/mathhelpforum @mathhelpforum