0
$\begingroup$

$S_n$ has $2^n$ subsets?

I don't understand how $S_{n+1}$ should have $2^{n+1}$ subsets instead of $2^n + 1$ subsets.

$S_{n+1} = \{s_1,s_2,\ldots,s_n, s_{n+1}\}$

There is only 1 more elements! No?

  • 2
    Okay; **now** it makes sense.2012-11-16

3 Answers 3

4

Let’s look at a simple example. The $2$-element set $S_2=\{0,1\}$ has four subsets: $\varnothing,\{0\},\{1\}$, and $\{0,1\}$. Now expand it to $S_3=\{0,1,2\}$. Here are the subsets:

$\begin{array}{c|c} \text{Already subsets of }S_2&\text{New subsets}\\ \hline \varnothing&\{\color{red}{2}\}\\ \{0\}&\{0,\color{red}{2}\}\\ \{1\}&\{1,\color{red}{2}\}\\ \{0,1\}&\{0,1,\color{red}{2}\} \end{array}$

The number of subsets has doubled, not just increased by $1$. The reason is that we have all of the old subsets of $S_2$ and also the four sets obtained by adding the element $2$ to each of the old subsets.

The same idea works not just for $S_2$, but for any $S_n$.

2

Your $2^{n+1}$ means there are double the subsets, but you are seeing only one more, right?.

When you have a problem like this, try a small example and see if it helps.

The set $\{1,2\}$ has four subsets: $\{\}, \{1\}, \{2\}$ and $\{1,2\}$. Now try listing the subsets of $\{1,2,3\}$. There should be 8.

1

$S_0=\{\}$ has no elements, but $1$ subset, namely $\{\}$.

If $S_n$ has $P_n$ subsets, then $S_{n+1}$ has $2P_n$ subsets; it has the $P_n$ subsets that $S_n$ had, then for each of those $P_n$ subsets, it has another subset with the $n+1^{\text{st}}$ element as well. Thus, $P_{n+1}=2P_n$.

Putting these two statements together, we get that $P_n=2^n$.