What is the principle?

The principle of mathematical induction says: if P(1) is true (the base step), and if for every integer k ≥ 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.

For n=1: left-hand side = 1^2 = 1. Right-hand side = 1 · 2 · 36 = 66 = 1. So P(1) is true.

What is inductive hypothesis?

Assume for some integer k ≥ 1:

QLDSpecialist MathematicsSyllabus dot point

Topic 1: Proof by mathematical induction

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

A focused answer to the QCE Specialist Mathematics Unit 3 dot point on proof by mathematical induction. Covers the base step and inductive step structure, summation proofs, divisibility arguments and inequality proofs, with the precise wording QCAA markers reward and the inductive-hypothesis logic that earns full method marks.

Generated by Claude Opus 4.76 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

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.

Worked example

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

Base step. For $n=1$ : left-hand side $= 1^2 = 1$ . Right-hand side $= \dfrac{1 \cdot 2 \cdot 3}{6} = \dfrac{6}{6} = 1$ . So $P(1)$ is true.

Inductive hypothesis. Assume for some integer $k \geq 1$ :

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

Inductive step. Consider $P(k+1)$ . Add the next term $(k+1)^2$ :

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

Take out the common factor $\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 the formula with $n$ replaced by $k+1$ , since $2(k+1)+1 = 2k+3$ . Therefore $P(k+1)$ holds.

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

Exam-style practice questions

Practice questions written in the style of QCAA exam questions on this dot point, with worked answer explainers. The year tag is the paper they imitate, not the source.

2023 QCAA5 marksThe 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.