# How many subsets does $S_{n+1}$ have?

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

-
I’m guessing that you mean $S_n$ and $S_{n+1}$. Unfortunately, you haven’t given us any idea of how these sets are defined; you’ll have to add that before anyone can give you a useful answer. –  Brian M. Scott Nov 16 '12 at 0:12
err sorry i meant 2^n –  George Nov 16 '12 at 0:48
But you still haven’t told us what the sets $S_n$ are! –  Brian M. Scott Nov 16 '12 at 0:53
it's a set with n elements –  George Nov 16 '12 at 0:53
Okay; now it makes sense. –  Brian M. Scott Nov 16 '12 at 0:54

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

-

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.

-

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

-