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

Sure, here is the proof using mathematical induction:

Step 1: Base Case For n=0, a set with no elements (empty set) has 1 subset, which is the empty set itself. Since 2^0 = 1, the statement holds for n=0.

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

Consider adding an (k+1)th element to the set. Each existing subset can remain as it is, or can include this new element. Therefore, each existing subset generates two subsets in the expanded set.

So, if a set with k elements has 2^k subsets, then a set with k+1 elements has 2 * 2^k = 2^(k+1) subsets.

Step 3: Conclusion By mathematical induction, the statement is true for all positive integers n. So, a set with n elements has 2^n subsets.