Establish by mathematical induction that a set having $n$ elements has $2^n$ subsets.

Question

I know the steps to an induction proof. The first step is to establish that $n=1$ is true. Then the second step is to assume that if we replaced $n$ by $k$, $2^k$ is true. For the third step, assuming the assumption is true, prove that $2^{k+1}$ is true. Well, the problem is, what do I set $2^k$ equal to and what do I set $2^{k+1}$ equal to?

Answer 1

If $n=k$ is true, then there are $2^k$ subsets $X_i$ of {$1,2,...,k$}.

Now any subset of {$1,2,...,k,k+1$} either does not contain $k+1$, and therefore is one of the $X_i$ from above, or it does contain $k+1$, in which case it is of the form $X_i$ U {$k+1$}, so there are $2^k+2^k=2^{k+1}$ subsets

Answer 2

Hint: Let $S_{k + 1} = \{s_1, \ldots, s_k, s_{k + 1}\}$ be our set of $k + 1$ elements. We want to show that $S_{k + 1}$ has exactly $2^{k + 1}$ subsets. Indeed, notice that any subset $T$ of $S_{k + 1}$ falls under $1$ of $2$ cases:

• Case 1: Suppose that $s_{k + 1} \in T$. Then we can rewrite $T$ in the form $T = T' \cup \{s_{k + 1}\}$, where $T'$ is any subset of $S_k = \{s_1, \ldots, s_k\}$. But hey, now we can apply the induction hypothesis!

• Case 2: Suppose that $s_{k + 1} \notin T$. Then $T$ is actually a subset of $S_k = \{s_1, \ldots, s_k\}$. But hey, now we can apply the induction hypothesis!

Conclude by adding up the number of subsets from Case 1 and Case 2.

Spoiler alert: You should get $2^{k + 1}$.