§-Syllabus dot point

SASpecialist MathematicsSyllabus dot point

How can we prove that a statement is true for every positive integer without checking infinitely many cases?

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

How to write a rigorous proof by mathematical induction: the base case, the inductive hypothesis, the inductive step, and the formal conclusion, with worked sum and divisibility examples.

Generated by Claude Opus 4.88 min answerUpdated 2026-06-02

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 proof
Proving a summation formula
Proving a divisibility result
Choosing the right starting value
Induction with inequalities
Common errors
Why it matters

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$ .

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

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 practice questions

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

SACE 20235 marksCalculator-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 20226 marksCalculator-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 20215 marksCalculator-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]