Proof by mathematical induction (WACE Year 12 Mathematics Specialist Unit 4)

Syllabus dot point

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

8 min readUpdated 2 Jun 2026

Quick answer

To prove a statement $P(n)$ holds for all integers $n \ge n_0$ , prove the base case $P(n_0)$ , then assume $P(k)$ (the inductive hypothesis) and use it to prove $P(k+1)$ . Together these two steps establish $P(n)$ for every $n \ge n_0$ . The three standard types are sums, divisibility and inequalities.

Jump to a section

What this dot point is asking
The structure of an induction
Summation proofs
Why induction proves a statement for all n
Divisibility proofs
Inequality proofs
How to set out a proof for full marks
The algebra of the inductive step
Exam-style questions

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 two steps of induction

Base case: show $P(n_0)$ is true for the smallest value. Inductive step: assume $P(k)$ is true for an arbitrary $k \ge n_0$ and deduce $P(k+1)$ . Conclusion: by induction $P(n)$ is true for all $n \ge n_0$ .

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.

Why induction proves a statement for all n

The logical force of induction is sometimes called the domino principle. The base case knocks over the first domino, and the inductive step guarantees that each fallen domino knocks over the next. Together they ensure every domino from the first onward falls, that is, $P(n)$ is true for every integer $n \ge n_0$ . Neither step alone is enough: a true base case without the inductive step says nothing about later values, and a valid inductive step without a base case has no starting point and proves nothing. This is why SCSA insists on both steps and a clear concluding statement.

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.

How to set out a proof for full marks

SCSA marks induction on structure as much as on algebra, so a disciplined layout matters. Begin by naming the statement: "Let $P(n)$ be the statement that ...". Verify the base case explicitly, computing both sides at the smallest value and stating that they agree. State the inductive hypothesis as "Assume $P(k)$ is true for some integer $k \ge n_0$ ", writing out exactly what is being assumed. Then aim to derive $P(k+1)$ , making the moment where the hypothesis is substituted clearly visible. Finish with the conclusion: "Hence by the principle of mathematical induction, $P(n)$ is true for all integers $n \ge n_0$ ." Omitting the base case, the explicit hypothesis, or the closing statement each costs marks even if the algebra is correct.

The algebra of the inductive step

The technical heart of a summation proof is rewriting the expression for $k$ plus the new term into the target form for $k+1$ . The reliable method is to take a common factor out of the assumed sum and the new term. In the sum-of-squares proof, both $\dfrac{k(k+1)(2k+1)}{6}$ and $(k+1)^2$ share the factor $(k+1)$ , so factoring it out leaves a quadratic in $k$ to simplify. For a divisibility proof, the key move is to write the expression at $k+1$ in terms of the expression at $k$ : for $7^{k+1} - 1$ , rewrite as $7 \cdot 7^k - 1$ and substitute $7^k = 6m + 1$ from the hypothesis. Recognising which algebraic manipulation exposes the hypothesis is the skill that separates a complete proof from a stalled one.

Worked example

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

Step 1: Name the statement

Giving the statement a name lets us refer to it precisely in every subsequent step. Let $P(n)$ be the statement that the sum of the first $n$ positive integers equals $\tfrac{n(n+1)}{2}$ .

Step 2: Verify the base case

The base case anchors the chain of reasoning; without it, there is nothing to build from. For $n = 1$ , the left side is $1$ and the right side is $\tfrac{1 \times 2}{2} = 1$ . Both sides agree, so $P(1)$ is true.

Step 3: Establish the inductive step

We assume $P(k)$ is true for some integer $k \ge 1$ and aim to deduce $P(k+1)$ . We assume $1 + 2 + \dots + k = \tfrac{k(k+1)}{2}$ and add the next term $k + 1$ to both sides:

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 the formula with $n = k + 1$ , so $P(k+1)$ is true whenever $P(k)$ is true.

Step 4: State the conclusion

Both conditions of the principle of mathematical induction have been satisfied: the base case holds and the inductive step is valid. By induction, $P(n)$ holds for all integers $n \ge 1$ .

Final answer: $1 + 2 + \dots + n = \dfrac{n(n+1)}{2}$ for all integers $n \ge 1$ .

Common traps

Assuming what you are proving: The hypothesis is $P(k)$ , not $P(k+1)$ . You assume the case $k$ and derive the case $k+1$ .
Skipping the base case: Without a verified base case the chain never starts, so the proof is incomplete.
Not using the hypothesis: A valid inductive step must actually substitute the assumed $P(k)$ ; otherwise it is not induction.

Exam-style questions

Questions in the style of SCSA exam questions on this dot point, each with a worked answer. They are written by ExamExplained unless tagged "Past paper"; the year shows the paper a question is modelled on.

WACE 2023-style7 marks

Calculator-free. Prove by mathematical induction that

\displaystyle\sum_{r=1}^{n} r^2 = \frac{n(n+1)(2n+1)}{6}

for all integers

n \ge 1

Show worked answer →

A standard summation induction.

Let $P(n)$ be the statement $\sum_{r=1}^{n} r^2 = \dfrac{n(n+1)(2n+1)}{6}$ .

Base case $n = 1$ : LHS $= 1$ ; RHS $= \dfrac{1 \cdot 2 \cdot 3}{6} = 1$ . True.

Inductive step: assume $P(k)$ , that $\sum_{r=1}^{k} r^2 = \dfrac{k(k+1)(2k+1)}{6}$ . Add the next term $(k+1)^2$ : $\dfrac{k(k+1)(2k+1)}{6} + (k+1)^2 = \dfrac{(k+1)\big[k(2k+1) + 6(k+1)\big]}{6} = \dfrac{(k+1)(2k^2 + 7k + 6)}{6} = \dfrac{(k+1)(k+2)(2k+3)}{6}$ . This is $P(k+1)$ , the formula with $n = k+1$ .

By induction $P(n)$ holds for all $n \ge 1$ . Markers reward the base case, the explicit hypothesis, the factorisation to the $k+1$ form, and the concluding statement.

WACE 2021-style6 marks

Calculator-free. Prove by mathematical induction that

7^n - 1

is divisible by

6

for all integers

n \ge 1

Show worked answer →

A divisibility induction.

Let $P(n)$ be the statement that $7^n - 1$ is divisible by $6$ .

Base case $n = 1$ : $7^1 - 1 = 6$ , divisible by $6$ . True.

Inductive step: assume $P(k)$ , so $7^k - 1 = 6m$ for some integer $m$ , i.e. $7^k = 6m + 1$ . Then $7^{k+1} - 1 = 7 \cdot 7^k - 1 = 7(6m + 1) - 1 = 42m + 7 - 1 = 42m + 6 = 6(7m + 1)$ , a multiple of $6$ . So $P(k+1)$ holds.

By induction $7^n - 1$ is divisible by $6$ for all $n \ge 1$ . Markers reward the base case, expressing $7^k$ from the hypothesis, factoring out $6$ at $k+1$ , and the conclusion.

Practise this

Sources & how we know this

Mathematics Specialist ATAR course: syllabus and support materials — SCSA
Past ATAR course examinations — SCSA