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.