Induction

It can often be hard to prove a statement when there are an infinite number of cases, as with statements involving the natural numbers. In these cases, a proof by induction is often possible and often simple. Proofs by induction have two steps.
1. The basis step. This involve showing that a statement is true for some natural number
$k$
.
This step is labelled
$P(k)$
.
2. Assume
$P(m)$
is true for
$m \ge k$
then prove
$P(m+1)$
is true.
A very simple example is: Prove
$n^2 \gt n$
for
$n \gt 1$
. 1. The basis step.
$P(2)$
is true since
$2^2 \gt 2$
. 2. Assume
$P(m)$
is true for
$m \gt 2$
.
$P(m+1)$
is the statement
$(m+1)^2 \gt (m+1)$
.
Expanding the brackets gives
$m^2+2m+1=m+1$

Use
$P(m)$
which states
$m^2 \gt m$
to give
$m+2m+1=m+1$

which simplifies to
$3m+1=m+1$

This is true for
$m \gt 2$