Show that "if" P(k) is valid, then P(k+1) "must therefore" also be valid.
Hence, write P(k+1) in terms of P(k).
If P(k) is valid, then
If , then P(k+1) will be valid.
It can be seen that this is true since
hence, you need to examine the case for