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

Add comment

Security code
Refresh