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

Steps:

1) $\displaystyle \forall S \in \text{Pow}(A), k \in S \text{ or } k \not\in S$

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

3) $\displaystyle \text{Let }A' = \{1,2,3,...,k-1\}\,\,\,\,

\\ \forall S \in \text{Pow}(A'), S \cup \{k\} \in \text{Pow}(A)$

These are the only subsets with k as their elements. But clearly there are $\displaystyle |\text{Pow}(A')|$ subsets. Again use Induction Hypothesis.

4) Sum up both possibilities and wrap it up