## 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\]