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?

  • 14
    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.2012-11-16
  • 0
    err sorry i meant 2^n2012-11-16
  • 0
    But you still haven’t told us what the sets $S_n$ are!2012-11-16
  • 0
    it's a set with n elements2012-11-16
  • 0
    ah my mistake. i messed up when i wrote the question.2012-11-16
  • 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$.