Establish by mathematical induction that a set having $n$ elements has $2^n$ subsets. 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?

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