What is not using the hypothesis?

A valid inductive step must actually substitute the assumed P(k); otherwise it is not induction.

WASpecialist MathematicsSyllabus dot point

How does proving a base case and an inductive step establish a statement for every natural number?

Prove statements by mathematical induction, including summation, divisibility and inequality results

WACE Specialist proof by mathematical induction: the base case and inductive step, the structure of a rigorous induction, and applying it to summation formulas, divisibility statements and inequalities, with a worked example.

Generated by Claude Opus 4.77 min answerUpdated 2026-05-29

Reviewed by: AI editorial process; not yet individually human-reviewed

Have a quick question? Jump to the Q&A page

Jump to a section

What this dot point is asking
The structure of an induction
Summation proofs
Divisibility proofs
Inequality proofs

What this dot point is asking

SCSA wants a rigorously structured induction: a clear base case, an explicit hypothesis, a worked inductive step that uses the hypothesis, and a concluding statement.

The structure of an induction

The logic is a chain: the base case starts it, and the inductive step passes truth from each integer to the next, so every integer from $n_0$ upward is reached.

Summation proofs

For a claimed sum formula, the base case checks $n = 1$ . The inductive step adds the $(k+1)$ th term to the assumed sum for $k$ and shows the total matches the formula at $k+1$ . The key algebra is to factor and rearrange the expression for $k$ plus the new term into the target form.

Divisibility proofs

To show an expression is divisible by $d$ for all $n$ , assume $P(k)$ means the expression at $k$ is a multiple of $d$ . Then write the expression at $k+1$ so that it contains the expression at $k$ (a multiple of $d$ by hypothesis) plus an extra term that is also a multiple of $d$ . The sum is then divisible by $d$ .

Inequality proofs

For an inequality, the inductive step starts from the assumed inequality at $k$ and adds or multiplies a term to reach the $k+1$ form, often showing the difference of the two sides has a definite sign.

Worked example

Prove by induction that $1 + 2 + 3 + \dots + n = \dfrac{n(n+1)}{2}$ for all $n \ge 1$

Let $P(n)$ be the statement that the sum of the first $n$ integers equals $\tfrac{n(n+1)}{2}$ .

Base case $n = 1$ : the left side is $1$ and the right side is $\tfrac{1\times 2}{2} = 1$ . True.

Inductive step: assume $P(k)$ , that $1 + 2 + \dots + k = \tfrac{k(k+1)}{2}$ . Add the next term $k+1$ :

1 + 2 + \dots + k + (k+1) = \frac{k(k+1)}{2} + (k+1) = (k+1)\left(\frac{k}{2} + 1\right) = \frac{(k+1)(k+2)}{2}.

This is exactly $P(k+1)$ , the formula with $n = k+1$ . So $P(k) \Rightarrow P(k+1)$ .

By induction, $P(n)$ holds for all integers $n \ge 1$ .