combinatorics - 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

Answer

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