# 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$.
• if at every step you have two choices and there is a total of $n$ steps, then there are $2^n$ number of possible choices. – mathemagician May 2 '13 at 2:10
Think of the binomial coefficient $$\left( \begin{array}{c} n \\ k \end{array}\right)$$ as the number of subsets of $\{x_1,x_2,\ldots,x_n\}$ that have $k$ elements. Then to find the total number of subsets, you want: $$\left( \begin{array}{c} n \\ 0 \end{array}\right)+\left( \begin{array}{c} n \\ 1 \end{array}\right)+\left( \begin{array}{c} n \\ 2 \end{array}\right)+\cdots +\left( \begin{array}{c} n \\ n \end{array}\right).$$How can you show this sum is equal to $2^n$? A clever binomial might do the trick.