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