Question: The empty set (∅) is a set with no elements. How many subsets does it have? How many subsets does the one-element set {1} have? How many subsets does the two-element {1, 2} set have? How many of these contain 2? How many subsets does {1, 2, 3} have? How many contain 3? Give a recurrence for the number S(n) of subsets of an n-element set, and prove by induction that your recurrence is correct.