Proof by mathematical induction (SACE Stage 2 Specialist Mathematics)

Syllabus dot point

“Mathematical induction proves a statement for all integers from a base value by establishing a base case and showing each case forces the next.”

8 min readUpdated 2 Jun 2026

Quick answer

Mathematical induction proves a statement $P(n)$ holds for all integers $n\ge n_0$ in two steps: prove the base case $P(n_0)$ is true, then prove the inductive step that $P(k)\Rightarrow P(k+1)$ for an arbitrary $k\ge n_0$ . Together these force $P(n)$ to be true for every integer from $n_0$ onward.

Jump to a section

What this dot point is asking
The structure of an induction proof
Proving a summation formula
Proving a divisibility result
Choosing the right starting value
Induction with inequalities
Common errors
Why it matters
Exam-style questions

What this dot point is asking

A statement like " $1+2+\cdots+n=\tfrac{n(n+1)}{2}$ for all positive integers $n$ " makes infinitely many claims at once. You cannot check them all. Mathematical induction is the standard tool for proving such statements rigorously.

The structure of an induction proof

Let $P(n)$ be the statement you want to prove for all integers $n\ge n_0$ (usually $n_0=1$ ). The proof has three parts that must always appear.

Base case. Show $P(n_0)$ is true by direct substitution.
Inductive step. Assume $P(k)$ is true for some arbitrary integer $k\ge n_0$ (this assumption is the inductive hypothesis). Using it, prove $P(k+1)$ is true.
Conclusion. State that, by the principle of mathematical induction, $P(n)$ is true for all integers $n\ge n_0$ .

Why two steps suffice

The base case is the first domino. The inductive step guarantees that whenever one domino falls, the next falls too. Together they knock down every domino from $n_0$ onward, so no individual case needs checking.

The logical engine is the implication $P(k)\Rightarrow P(k+1)$ . You are not assuming what you want to prove; you are assuming one case to derive the next.

Proving a summation formula

Sum of the first

n

positive integers

Worked example

Prove that $1+2+3+\cdots+n=\dfrac{n(n+1)}{2}$ for all integers $n\ge 1$ .

Step 1: Verify the base case

The base case confirms the first domino falls. Substitute $n=1$ into both sides of the formula and check they agree.

Left side $=1$ . Right side $=\dfrac{1(1+1)}{2}=1$ . So $P(1)$ is true.

Step 2: State the inductive hypothesis

Assume $P(k)$ holds for some arbitrary integer $k\ge 1$ . This assumption is the inductive hypothesis; it is not what we are trying to prove, but a tool to derive the next case.

1+2+\cdots+k=\frac{k(k+1)}{2}.

Step 3: Prove $P(k+1)$ using the hypothesis

We must show $P(k+1)$ : that $1+2+\cdots+(k+1)=\dfrac{(k+1)(k+2)}{2}$ .

Starting from the left side of $P(k+1)$ , split off the last term and replace the remaining sum with the hypothesis.

\underbrace{1+2+\cdots+k}_{=\,\frac{k(k+1)}{2}}+(k+1)=\frac{k(k+1)}{2}+(k+1).

Factor out $(k+1)$ :

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

This is exactly the right side of $P(k+1)$ , so $P(k)\Rightarrow P(k+1)$ .

Step 4: State the conclusion

Both conditions of the principle of mathematical induction are satisfied, so the chain of implications extends to every integer from $n=1$ onward.

By the principle of mathematical induction, the formula holds for all integers $n\ge 1$ .

Proving a divisibility result

Induction also proves divisibility statements. The trick is to rewrite the $k+1$ expression so the inductive hypothesis appears explicitly.

Divisibility by 3

Worked example

Prove that $4^n-1$ is divisible by $3$ for all integers $n\ge 1$ .

Step 1: Verify the base case

Check the statement is true for the smallest value, $n=1$ , by direct calculation.

$4^1-1=3$ , which is divisible by $3$ . So $P(1)$ is true.

Step 2: State the inductive hypothesis

Assume $P(k)$ holds for some integer $k\ge 1$ , meaning $4^k-1$ is divisible by $3$ . We write this as $4^k-1=3m$ for some integer $m$ , or equivalently $4^k=3m+1$ . This expression for $4^k$ is the key substitution in the next step.

Step 3: Prove $P(k+1)$ using the hypothesis

Write $4^{k+1}-1$ in a way that isolates $4^k$ , then substitute the hypothesis to reveal a factor of $3$ .

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

Since $4m+1$ is an integer, $4^{k+1}-1$ is divisible by $3$ . Thus $P(k)\Rightarrow P(k+1)$ .

Step 4: State the conclusion

The base case and the inductive step together satisfy the principle of mathematical induction.

By induction, $4^n-1$ is divisible by $3$ for all integers $n\ge 1$ .

Choosing the right starting value

Not every statement starts at $n=1$ . An inequality such as " $2^n>n^2$ " is false for $n=2,3,4$ but true from $n=5$ onward, so the base case must be $P(5)$ , and the conclusion claims the result only for $n\ge 5$ . Always read the range of $n$ in the question and set $n_0$ accordingly. The inductive step is unchanged - you still prove $P(k)\Rightarrow P(k+1)$ - but the domino chain begins at the stated starting value, so the base case substitution must use that value.

Induction with inequalities

Divisibility and summation are the two most common SACE induction tasks, but inequalities also appear. The structure is identical, except the inductive step manipulates an inequality rather than an equation. To show $P(k)\Rightarrow P(k+1)$ you typically start from the assumed inequality for $k$ , add or multiply both sides by the quantity that turns the $k$ expression into the $k+1$ expression, and then argue that the result is at least (or at most) the required bound. Keeping the direction of the inequality consistent through every step is the discipline examiners look for.

Common errors

Skipping or mis-stating the base case

A proof with no base case proves nothing, even with a perfect inductive step, because the chain of dominoes is never started. Always verify $P(n_0)$ explicitly. If the claim is for $n\ge 0$ or $n\ge 2$ , the base case must use that starting value, not automatically $n=1$ .

Assuming what you set out to prove

Do not assume $P(k+1)$ or $P(n)$ for all $n$ . The inductive hypothesis is the single statement $P(k)$ , and you must derive $P(k+1)$ from it. Working backwards from $P(k+1)$ to a true statement without a clear chain of equalities is not a valid proof.

Make the hypothesis visible

In the inductive step, write the $k+1$ expression so the $k$ case literally appears (split off the last term, or factor out a power). Then substitute the hypothesis. SACE markers reward a clearly labelled base case, hypothesis, step, and conclusion.

Why it matters

Mathematical induction is the foundation of rigorous proof in Specialist Mathematics and underpins results you will use later, including De Moivre's theorem in polar form. It also trains the precise, structured reasoning that the external examination and the Mathematical Investigation folio both reward.

Exam-style questions

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

SACE 2023-style5 marks

Calculator-free. Prove by mathematical induction that

4^n + 15n - 1

is divisible by

9

for all positive integers

n

Show worked answer →

Let $P(n)$ be the statement that $4^n + 15n - 1$ is divisible by $9$ .

Base case ( $n = 1$ ): $4^1 + 15(1) - 1 = 18 = 9 \times 2$ , divisible by $9$ , so $P(1)$ is true. [1 mark]

Inductive hypothesis: assume $P(k)$ , i.e. $4^k + 15k - 1 = 9m$ for some integer $m$ , so $4^k = 9m - 15k + 1$ . [1 mark]

Inductive step: $4^{k+1} + 15(k+1) - 1 = 4\cdot 4^k + 15k + 14 = 4(9m - 15k + 1) + 15k + 14 = 36m - 45k + 18 = 9(4m - 5k + 2)$ . [2 marks]

Since $4m - 5k + 2$ is an integer, $P(k+1)$ holds. By the principle of mathematical induction, $P(n)$ is true for all positive integers $n$ . [1 mark]

SACE 2022-style6 marks

Calculator-free. Use mathematical induction to prove that

\dfrac{1}{1\times 4} + \dfrac{1}{4\times 7} + \cdots + \dfrac{1}{(3n-2)(3n+1)} = \dfrac{n}{3n+1}

for all positive integers

n

Show worked answer →

Let $P(n)$ be the statement that the sum equals $\dfrac{n}{3n+1}$ .

Base case ( $n = 1$ ): left side $= \dfrac{1}{1\times 4} = \dfrac{1}{4}$ ; right side $= \dfrac{1}{4}$ . So $P(1)$ is true. [1 mark]

Inductive hypothesis: assume $P(k)$ : the sum to $k$ terms is $\dfrac{k}{3k+1}$ . [1 mark]

Inductive step: add the $(k+1)$ th term $\dfrac{1}{(3k+1)(3k+4)}$ :

\frac{k}{3k+1} + \frac{1}{(3k+1)(3k+4)} = \frac{k(3k+4) + 1}{(3k+1)(3k+4)} = \frac{3k^2 + 4k + 1}{(3k+1)(3k+4)}. \;[\text{2 marks}]

Factorise the numerator $3k^2 + 4k + 1 = (3k+1)(k+1)$ , giving $\dfrac{(k+1)}{3(k+1)+1}$ , which is $P(k+1)$ . [1 mark]

Since $P(1)$ holds and $P(k) \Rightarrow P(k+1)$ , by induction $P(n)$ is true for all positive integers $n$ . [1 mark]

SACE 2021-style5 marks

Calculator-free. Prove by mathematical induction that

5^n - 1

is divisible by

4

for all positive integers

n

Show worked answer →

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

Base case ( $n = 1$ ): $5^1 - 1 = 4 = 4\times 1$ , divisible by $4$ , so $P(1)$ is true. [1 mark]

Inductive hypothesis: assume $P(k)$ : $5^k - 1 = 4m$ for some integer $m$ , so $5^k = 4m + 1$ . [1 mark]

Inductive step: $5^{k+1} - 1 = 5\cdot 5^k - 1 = 5(4m + 1) - 1 = 20m + 4 = 4(5m + 1)$ . [2 marks]

Since $5m + 1$ is an integer, $P(k+1)$ holds. By the principle of mathematical induction, $P(n)$ is true for all positive integers $n$ . [1 mark]

Practise this

Sources & how we know this

Stage 2 Specialist Mathematics subject outline (2025 onwards) — SACE Board
Stage 2 Specialist Mathematics: external assessment — SACE Board

What this dot point is asking

The structure of an induction proof

Proving a summation formula

Worked example

Step 1: Verify the base case

Step 2: State the inductive hypothesis

Step 3: Prove P(k+1)P(k+1)P(k+1) using the hypothesis

Step 4: State the conclusion

Proving a divisibility result

Worked example

Step 1: Verify the base case

Step 2: State the inductive hypothesis

Step 3: Prove P(k+1)P(k+1)P(k+1) using the hypothesis

Step 4: State the conclusion

Choosing the right starting value

Induction with inequalities

Common errors

Why it matters

Exam-style questions

Practise this

Sources & how we know this

Step 3: Prove $P(k+1)$ using the hypothesis

Step 3: Prove $P(k+1)$ using the hypothesis