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.

2. 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: $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

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

4. 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: $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.
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$.