Question: 1. Using induction, prove that 10n2 for n ≥ 11.
2. Prove that any set with n elements has 2n subsets, using induction. The proof in Example for the subsets of {1,...,k} may inspire you.
Example: We have the sets {1},{1,2},{1,2,3},... {1,2,3,...,k},... and so on. We want to show that the set of the first n natural numbers has 2n subsets. (Yes, we already know this as a special case of Theorem. But
(a) it's always good to have more than one proof of a theorem, and
(b) we need an example that isn't too weird, i.e., doesn't contain any Vogelplexes.)
Theorem: A set with n elements has 2n subsets.
It is useful to have different proofs of the same theorem because they give different understandings of, or different perspectives on, the mathematics involved. Hidden in the above proofs is the following.