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

Sure, let's use the principle of mathematical induction to prove this.

Step 1: Base Case Let's start with the smallest possible set, a set with no elements (the empty set). The empty set has exactly one subset, which is the set itself. So, for n=0, the number of subsets is 2^0 = 1, which is true.

Step 2: Inductive Hypothesis Assume that the statement is true for some k, i.e., a set with k elements has 2^k subsets.

Step 3: Inductive Step We need to prove that the statement is also true for k+1, i.e., a set with k+1 elements has 2^(k+1) subsets.

Consider adding an (k+1)th element to our set. Each existing subset can remain as it is, or it can include this new element. This means that every subset of the original set corresponds to exactly two subsets of the new set: one with the (k+1)th element and one without it.

So, the number of subsets of the new set is twice the number of subsets of the original set. In other words, if the original set has 2^k subsets, then the new set has 2 * 2^k = 2^(k+1) subsets.

Therefore, by mathematical induction, a set with n elements has 2^n subsets.