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?



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

  • $\begingroup$ thanks for the answer!, though i don't really understand the last part about. i.e how did you find the total number of strings possible based on the multiplication rule $\endgroup$ – Krimson May 2 '13 at 2:05
  • 1
    $\begingroup$ 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. $\endgroup$ – 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.