How to do a combinatorial proof I have a question which asked for a combinatorial proof. I have no clue how to do do a combinatorial proof. 
The question is
prove that the total number of subsets in $\{x_1, x_2, x_3, ... ,x_n\}$ is $2^n$
I understand how it works. As in
for n=2 we have 
$ {2 \choose 1} + {2 \choose 2}  + 1= 4$  
for n=3 we have 
$ {3 \choose 1} + {3 \choose 2}  + {3 \choose 3} + 1= 8$  
and so on.
So there is a pattern which can be generalised with $2^n$
but how would i show this using a combinatorial proof? I dont even now where to start. Could you lead me?
Thanks

This is quite simple. You want the total number of subsets formed from $\{x_1, x_2, x_3, ... ,x_n\}$. Now, say $S$ is a subset. Ask yourself, "Is $x_1$ in $S$?" You have two choices, yes or no. Then ask yourself, "Is $x_2$ in $S$?", again two choices. Do this for all $x$'s. Every string of answers will define a unique subset $S$, clearly. The multiplication rule tells you that the total number of strings will be $2\cdot 2\cdot 2\dots 2=2^n$. 
