# Math Help - Induction

1. ## Induction

Use induction to prove that a finite set with n elements has 2^n subsets.

2. See here:

http://www.cs.uiuc.edu/class/fa08/cs...es/lect_17.pdf

The statement holds for $n=1$: $\emptyset \subseteq \left\{ 1 \right\}\;\& \;\left\{ 1 \right\} \subseteq \left\{ 1 \right\}$.
Now suppose that $S = \left\{ {1,2, \cdots ,k} \right\}$ and $S$ has $2^k$ subsets.
Consider $S^+=S \cup \left\{ {k + 1} \right\}$. Each subset of $S$ is also a subset of $S^+$ this is $2^k$ subsets. Unite each subset of $S$ with $\left\{k+1\right\}$ giving us $2^k$ subsets more subsets. So we have $2^k + 2^k = 2\left( {2^k } \right) = 2^{k + 1}$ subsets of $S^+$. That completes the induction.