Mathematical induction (QCE Specialist Mathematics Unit 3)

Syllabus dot point

“Understand and use the principle of mathematical induction to prove results involving sums of series, divisibility statements and inequalities for all positive integers, structuring the base step and the inductive step correctly”

6 min readUpdated 29 May 2026

Quick answer

Mathematical induction proves $P(n)$ for all positive integers in two steps: a base step verifying $P(1)$ (or the smallest valid $n$ ), and an inductive step assuming $P(k)$ and proving $P(k+1)$ . For sums, peel off the last term and substitute the hypothesis; for divisibility, write $f(k+1)$ in terms of $f(k)$ ; for inequalities, chain inequalities from the hypothesis. End with the standard conclusion citing the principle.

Jump to a section

What this dot point is asking
The answer
Exam-style questions

What this dot point is asking

QCAA wants you to prove a statement $P(n)$ holds for every positive integer $n$ using the principle of mathematical induction. You must set out two distinct steps clearly, state the inductive hypothesis explicitly, and finish with a logical conclusion. Induction appears in IA2 and the external assessment, and the marks are awarded as much for structure and communication as for algebra.

The answer

The principle

The principle of mathematical induction says: if $P(1)$ is true (the base step), and if for every integer $k \geq 1$ the truth of $P(k)$ implies the truth of $P(k+1)$ (the inductive step), then $P(n)$ is true for all positive integers $n$ .

Think of an infinite line of dominoes. The base step knocks over the first one. The inductive step guarantees that each falling domino topples the next. Together they guarantee every domino falls.

The standard layout

Every induction proof should be written in four labelled parts.

Base step. Show $P(1)$ is true by direct substitution. State both sides and confirm they are equal.
Inductive hypothesis. Assume $P(k)$ is true for some integer $k \geq 1$ . Write the statement $P(k)$ in full.
Inductive step. Using the hypothesis, prove $P(k+1)$ . This is the work: manipulate the left-hand side of $P(k+1)$ so the assumed $P(k)$ can be substituted in.
Conclusion. State that since $P(1)$ is true and $P(k)$ true implies $P(k+1)$ true, by the principle of mathematical induction $P(n)$ is true for all positive integers $n$ .

Summation proofs

The most common type is a closed form for a sum. To prove

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

assume $\sum_{r=1}^{k} r = \frac{k(k+1)}{2}$ . For $P(k+1)$ the left-hand side is the previous sum plus the new term $(k+1)$ :

\sum_{r=1}^{k+1} r = \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$ replaced by $k+1$ , so $P(k+1)$ holds. The key move is always to peel off the last term and substitute the hypothesis for the rest.

Divisibility proofs

To prove $d \mid f(n)$ for all $n$ , write $f(k)$ as a multiple of $d$ in the hypothesis, then express $f(k+1)$ in terms of $f(k)$ . For example, to show $3 \mid (4^n - 1)$ , assume $4^k - 1 = 3m$ for some integer $m$ . Then

4^{k+1} - 1 = 4 \cdot 4^k - 1 = 4(4^k - 1) + 3 = 4(3m) + 3 = 3(4m + 1).

Since $4m+1$ is an integer, $4^{k+1}-1$ is divisible by $3$ . The technique is to add and subtract to manufacture a copy of $f(k)$ .

Inequality proofs

For inequalities such as $2^n > n^2$ for $n \geq 5$ , the base step uses $n = 5$ (not $n=1$ , because the claim fails for small $n$ ). State the restricted starting value. In the inductive step you typically chain inequalities: start from $2^{k+1} = 2 \cdot 2^k$ , apply the hypothesis $2^k > k^2$ , then show $2k^2 \geq (k+1)^2$ for the relevant $k$ . Always justify each inequality you use.

Prove

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

for all positive integers

n

Step 1: Base step

Verify the formula for $n = 1$ by direct substitution. The left-hand side has only one term:

\text{LHS} = 1^2 = 1

The right-hand side with $n = 1$ is:

\text{RHS} = \frac{1 \cdot 2 \cdot 3}{6} = \frac{6}{6} = 1

Since LHS $=$ RHS, the statement $P(1)$ is true.

Step 2: Inductive hypothesis

Assume the formula holds for some particular integer $k \geq 1$ , that is, assume:

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

This assumption is what we are allowed to use in the next step.

Step 3: Inductive step

We must prove $P(k+1)$ , which claims the sum up to $k+1$ equals $\dfrac{(k+1)(k+2)(2k+3)}{6}$ . Start from the left-hand side of $P(k+1)$ and peel off the last term so the inductive hypothesis can be applied:

\sum_{r=1}^{k+1} r^2 = \underbrace{\sum_{r=1}^{k} r^2}_{\text{apply hypothesis}} + (k+1)^2 = \frac{k(k+1)(2k+1)}{6} + (k+1)^2

Factor out $\dfrac{k+1}{6}$ :

= \frac{k+1}{6}\Big[k(2k+1) + 6(k+1)\Big] = \frac{k+1}{6}\big[2k^2 + 7k + 6\big]

Factorise the quadratic: $2k^2 + 7k + 6 = (k+2)(2k+3)$ . So:

\sum_{r=1}^{k+1} r^2 = \frac{(k+1)(k+2)(2k+3)}{6}

This is exactly the formula with $n$ replaced by $k+1$ (since $2(k+1)+1 = 2k+3$ ), so $P(k+1)$ holds.

Step 4: Conclusion

Since $P(1)$ is true and the truth of $P(k)$ implies the truth of $P(k+1)$ , by the principle of mathematical induction the result holds for all positive integers $n$ .

Final answer: $\displaystyle\sum_{r=1}^{n} r^2 = \dfrac{n(n+1)(2n+1)}{6}$ for all positive integers $n$ .

Common trap

A frequent error is "proving" the inductive step by assuming what you want to show. Do not write $P(k+1)$ on both sides and simplify to $0=0$ ; that assumes the conclusion. Instead start from one side of $P(k+1)$ (usually the sum) and transform it using the hypothesis until it equals the other side. Also do not forget the explicit inductive hypothesis line, and never omit the final conclusion sentence: markers award a communication mark for it.

Exam-style questions

Questions in the style of QCAA 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.

Practice5 marks

The sum of a geometric progression with n terms, where the first term is 1 and the common ratio is r, is given by S_n = (1 - r^n) / (1 - r). Prove that this rule is true using mathematical induction by completing the steps of the proof as indicated. a) Initial statement. b) Inductive step (assuming the rule is true for n = k). c) Conclusion.

Show worked answer →

a) Initial statement [1 mark]: Let n = 1. LHS = the sum of one term = 1. RHS = (1 - r^1)/(1 - r) = (1 - r)/(1 - r) = 1. LHS = RHS, so the rule is true for n = 1.

b) Inductive step [3 marks]: Assume the rule holds for n = k, i.e. 1 + r + r^2 + ... + r^(k-1) = (1 - r^k)/(1 - r).
Required to prove S_(k+1) = (1 - r^(k+1))/(1 - r). The (k+1)th sum is S_k plus the next term r^k:
S_(k+1) = (1 - r^k)/(1 - r) + r^k
= (1 - r^k + r^k(1 - r))/(1 - r)
= (1 - r^k + r^k - r^(k+1))/(1 - r)
= (1 - r^(k+1))/(1 - r).
This is the rule with n = k + 1, so the result holds for n = k + 1.

c) Conclusion [1 mark]: The rule is true for n = 1, and its truth for n = k implies its truth for n = k + 1. By the principle of mathematical induction, the rule is true for all positive integers n.

Practise this

Sources & how we know this

Specialist Mathematics General senior syllabus 2025 — QCAA