Induction the number of subsets is 2 to the n

Statement

Prove by induction on $n$ that every set with $n$ elements has exactly $2^n$ subsets.

Solution

Base ($n=0$): the only set with $0$ elements is $\varnothing$, which has a single subset (itself), and $2^0 = 1$. True.

Inductive step: assume every set with $k$ elements has $2^k$ subsets. Let $S$ have $k+1$ elements; fix an element $e \in S$ and set $S' = S \setminus \{e\}$, which has $k$ elements.

The subsets of $S$ split into two groups:

• those that do not contain $e$: exactly the subsets of $S'$, so $2^k$ of them;
• those that do contain $e$: obtained by adding $e$ to a subset of $S'$, so again $2^k$.

In total $2^k + 2^k = 2 \cdot 2^k = 2^{k+1}$ subsets. By the principle of induction the claim holds for all $n$. $\blacksquare$