For all n >= 0, if |S| = n, then |2S| = 2n

For all n ≥ 0, if |S| = n, then |2^S| = 2ⁿ

Proof by induction on n.
Base case: Consider a set S with 0 elements.
Then S = ∅ so 2^S = {∅}.

Inductive hypothesis: Let k ≥ 0 be any integer.
Assume that any set with k elements has 2^k subsets.

Let S be any set with k + 1 elements.
Suppose S = {x₁, x₂, x₃, ..., x_k, x_{k + m}}.

The set of all subsets of S can be listed in two lists.

1. First, list all the subsets of {x₁, x₂, x₃, ..., x_k}. (These are the subsets that do not contain x_{k + 1}).
2. Second, take each of the subsets in the first list and add x_{k + 1} to the subset. (These are the subsets that do contain x_{k + 1}).

By the inductive hypothesis, there are 2^k subsets in the first list and 2^k subsets in the second list.

So |2^S| = 2ⁿ + 2^k = 2¹ * 2^k = 2^{k + 1}

By the proof of mathematical induction, if |S| = n, then |2^S| = 2ⁿ.

---

Furthering this concept

This proof by induction demonstrated a method of showing that the number of elements in the power set is equal to 2 raised to the power of the number of elements in the set.

What we do not necessarily see in this proof is the fact that this is actually a recursive process.

If we take an example set S, such that S = {a, b, c}, then we should be able to make the following statements about S:

1. Subsets of S that do not contain c include: ∅, {a}, {b}, {a, b}.
2. Subsets of S that contain c include: {c}, {a, c}, {b, c}, {a, b, c}.

Looking back at the original problem that we proved, we can see that this remain true for S since:

• |S| = 3
• 2^S = ∅, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}
• |2^S| = 2³ = 8

Since this is true, then we should be able to prove that the same is true for a set S such that S = {a, b, c, d}.