HSC Mathematics Advanced, Extension 1, and Extension 2/3-Unit/HSC/Induction

Induction is a form of proof useful for proving equations involving non-closed expressions (i.e., expressions with $n$ terms; sequences).

Explanation

Induction involves first proving that the equation is true for $n=1$, then proving true for $n=k+1$ (assuming for the purpose of the proof that the equation holds true for $n=k$). Since it is true for $n=k$ and true for $n=k+1$, and also true for $n=1$, it is true for $n=2$. It follows that it is true for all positive integers $n$.

Examples

Proving the formula for the sum of a series

Q: Prove by mathematical induction that for all integers $n\ge 1$,

$1^3+2^3+3^3+4^3+\cdots +n^3=(1+2+3+....n{)}^2$

A:

1. When $n=1$, $1^3=1=\frac{1}{4}(1{)}^2((1)+1{)}^2=\frac{1}{4}(4)=1$, so it is true for $n=1$
2. Suppose that the statement is true for $k,k\in \mathbb{N}$. That is, suppose that $1^3+2^3+3^3+4^3+\cdots +k^3=\frac{1}{4}{k}^2(k+1{)}^2$. This is sometimes called the induction hypothesis.
3. Then prove the statement for $n=k+1$ (that is, prove that $1^3+2^3+3^3+\cdots +(k+1{)}^3=\frac{1}{4}(k+1{)}^2(k+2{)}^2$:

   $\begin{array}{cc}\text{LHS}& =1^3+2^3+3^3+4+3+\cdots +k^3+(k+1{)}^3\\ & =\frac{1}{4}{k}^2(k+1{)}^2+(k+1{)}^3& \text{ (by the induction hypothesis)}\\ & =\frac{1}{4}(k+1{)}^2(k^2+4(k+1))\\ & =\frac{1}{4}(k+1{)}^2(k^2+4k+4)\\ & =\frac{1}{4}(k+1{)}^2(k+2{)}^2\\ & =\text{RHS}\end{array}$

4. It follows from parts 1 and 2 by mathematical induction that the statement is true for all positive integers $n$.