# HSC Extension 1 and 2 Mathematics/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 = \tfrac{1}{4} (1)^2((1)+1)^2 = \tfrac{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 = \tfrac{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 = \tfrac{1}{4} (k+1)^2(k+2)^2$:
\begin{align} \mbox{LHS} & = 1^3 + 2^3 + 3^3 + 4+3 + \cdots + k^3 + (k+1)^3 \\ & = \tfrac{1}{4} k^2 (k+1)^2 + (k+1)^3 & \mbox{ (by the induction hypothesis)} \\ & = \tfrac{1}{4}(k+1)^2(k^2 + 4(k+1)) \\ & = \tfrac{1}{4}(k+1)^2(k^2 + 4k + 4) \\ & = \tfrac{1}{4}(k+1)^2(k+2)^2 \\ & = \mbox{RHS} \end{align}
4. It follows from parts 1 and 2 by mathematical induction that the statement is true for all positive integers $n$.