Prove by induction on n: If a set A has n elements, its power set has 2^n elements.
*Given a set A, the power set of A is the set of all subsets of A
P(k)
The power of a set with k elements is
P(k+1)
The power of a set with k+1 elements is
Show that P(k+1) must be true if P(k) is true.
If a set of k elements has a power of
then an added element will form new subsets as it can be placed with all existing subsets.
Therefore a set of k+1 elements has a power of if a set of k elements has power
Finally prove for the base case.