Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
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. –  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
2  
Okay; now it makes sense. –  Brian M. Scott Nov 16 '12 at 0:54
show 1 more comment

3 Answers 3

up vote 4 down vote accepted

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

share|improve this answer
add comment

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.

share|improve this answer
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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