Claim: P(k) = "the power set of A={1,...,k} has 2^k elements of A".

Steps:

1)

2) If we forget k, then there are k-1 elements. So use induction hypothesis.

3)

These are the only subsets with k as their elements. But clearly there are subsets. Again use Induction Hypothesis.

4) Sum up both possibilities and wrap it up