Thread: 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: + +...+ =

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= possibilities. Hence, RHS=LHS.

Originally Posted by Chris11

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: + +...+ =

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= possibilities. Hence, RHS=LHS.

I can't see how you think the above proves anything...The easiest way to prove it is algebraically:

Tonio

@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.....

Originally Posted by Chris11

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: + +...+ =

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= 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 .

I have had a very hard time learning combinatorial proofs. I am just now beginning to understand how to do them.