A-level Mathematics/OCR/FP1/Mathematical Induction

Proof by induction is a method of deductive reasoning that produces a fully rigorous mathematical proof:

• Step 1 Prove that the result is true for a starting value, such as $n=1$ . This is called the basis case.
• Step 2 Assume that the result is true for some value, $k$
• Step 3 Prove that if it is true for $n=k$ , it is true for $n=k+1$ .
• Step 4 Conclude that the proposition is true for all positive integers.

Since we have proved the result for a general value, $k$ , then if we prove it for the next value, $k+1$ , we can logically conclude that it will be true for the next value, and the next, and the next, and so on ad infinitum.

An Example

Prove that the sequence: $1+2+3+\cdots +n={\frac {n(n+1)}{2}}$

Step 1: when $n=1$ : LHS = $1$ , RHS = ${\frac {1(1\cdot 2)}{2}}=1$ . Therefore, we have proved the hypothesis for one value...

Step 2: Now let $n=k$ , and prove this.

Let us use the symbol $s$ to represent the series $1+2+3+\cdots +(k-2)+(k-1)+k$

However, $s$ also represents $k+(k-1)+(k-2)+\cdots +3+2+1$ (which is the same series, but in a different order)

If we add the two series together, we get:

$2s=(k+1)+(k+1)+(k+1)+\cdots +(k+1)+(k+1)+(k+1)=k(k+1)$

$s={\frac {k(k+1)}{2}}$

Step 3: Now let $n=k+1$:

$1+2+3+\cdots +k+(k+1)={\frac {(k+1)(k+2)}{2}}$

However, the part in italics of the above line, is already known. Thus:

$s+(k+1)={\frac {(k+1)(k+2)}{2}}$

${\frac {k(k+1)}{2}}+(k+1)={\frac {(k+1)(k+2)}{2}}$

When we expand the left hand side, we get:

${\frac {k^{2}}{2}}+{\frac {3k}{2}}+1={\frac {k^{2}+3k+2}{2}}={\frac {(k+1)(k+2)}{2}}$

Step 4 The left hand side of the equation is equal to the right hand side, so therefore we can conclude that, by the principle of mathematical induction, since it is true for $n=1$ , and since if it is true for $n=k$ then it is true for $n=k+1$ , it is true for any positive integer.

Another Example

Prove that the sequence: $\sum {r^{2}}={\frac {n(n+1)(2n+1)}{6}}$

Step 1:

Prove true when $n=1$

$1^{2}={\frac {1(1+1)(2+1)}{6}}$

$1={\frac {6}{6}}$

LHS = RHS therefore true

Step 2:

Assume true when $n=k$

$1+4+9+\cdots +k^{2}={\frac {k(k+1)(2k+1)}{6}}$

Step 3:

Prove true when $n=k+1$

$1+4+9+\cdots +k^{2}+(k+1)^{2}={\frac {(k+1)(k+1+1)(2(k+1)+1)}{6}}$

We have assumed that $1+4+9+\cdots +k^{2}={\frac {k(k+1)(2k+1)}{6}}$ is true. So we can now assume that ${\frac {k(k+1)(2k+1)}{6}}+(k+1)^{2}={\frac {k(k+1)(k+1+1)(2(k+1)+1)}{6}}$

will also be true. However this time we need to prove it as well. This bit can get confusing, but all we have to rearrange each side so that we can see they are equal.

${\frac {(k+1)(k(2k+1)+6(k+1))}{6}}={\frac {(k+1)((k+1+1)(2(k+1)+1))}{6}}$ (LHS: took out a factor of ${\tfrac {k+1}{6}}$ ) (RHS: nothing)

${\frac {(k+1)(2k^{2}+7k+7)}{6}}={\frac {(k+1)((k+2)(2k+3))}{6}}$ (LHS: expanded the brackets) (RHS: simplified the brackets)

${\frac {(k+1)(k+2)(2k+3)}{6}}={\frac {(k+1)((k+2)(2k+3))}{6}}$ (LHS: factorized brackets) (RHS: nothing)

RHS = LHS therefore true

This is part of the FP1 (Further Pure Mathematics 1) module of the A-level Mathematics text.