Left side =1. Right side =1(1+1)2=1. So P(1) is true.

What is inductive step?

Assume P(k) holds for some integer k 1, that is $1+2++k=(k(k+1))/(2).We must showP(k+1): that1+2+\cdots+(k+1)=\dfrac{(k+1)(k+2)}{2}$.

SACE Board 2023 SACE Stage 2-style practice: Prove by mathematical induction that 4^n + 15n - 1 is divisible by 9 for all positive integers n.

Let P(n) be the statement that 4^n + 15n - 1 is divisible by 9. 1. Base case (n = 1). 4^1 + 15(1) - 1 = 4 + 15 - 1 = 18 = 9 x 2, which is divisible by 9, so P(1) is true. [1 mark] 2. Inductive hypothesis. Assume P(k) is true for some positive integer k, i.e. 4^k + 15k - 1 = 9m for some integer m, so 4^k = 9m - 15k + 1. [1 mark] 3. Inductive step. Consider P(k+1): 4^(k+1) + 15(k+1) - 1 = 4 x 4^k + 15k + 14. Substitute 4^k: = 4(9m - 15k + 1) + 15k + 14 = 36m - 60k + 4 + 15k + 14 = 36m - 45k + 18 = 9(4m - 5k + 2). [2 marks] 4. Since 4m - 5k + 2 is an integer, 4^(k+1) + 15(k+1) - 1 is divisible by 9, so P(k) true implies P(k+1) true. By the principle of mathematical induction, P(n) is true for all positive integers n. [1 mark]

SACE Board 2018 SACE Stage 2-style practice: Prove by mathematical induction that 5^n - 1 is divisible by 4 for all positive integers n.

Let P(n) be the statement that 5^n - 1 is divisible by 4. 1. Base case (n = 1). 5^1 - 1 = 4 = 4 x 1, divisible by 4, so P(1) is true. [1 mark] 2. Inductive hypothesis. Assume P(k) is true: 5^k - 1 = 4m for some integer m, so 5^k = 4m + 1. [1 mark] 3. Inductive step. Consider 5^(k+1) - 1 = 5 x 5^k - 1 = 5(4m + 1) - 1 = 20m + 5 - 1 = 20m + 4 = 4(5m + 1). [2 marks] 4. Since 5m + 1 is an integer, 5^(k+1) - 1 is divisible by 4, so P(k) implies P(k+1). By the principle of mathematical induction, P(n) holds for all positive integers n. [1 mark]

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

Jump to a section

What this dot point is asking
The structure of an induction proof
Proving a summation formula
Proving a divisibility result
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$ .

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

Inductive step. Assume $P(k)$ holds for some integer $k\ge 1$ , that is

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

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)$ and using 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)

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

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.

2023 SACE Stage 25 marksProve 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 = 4 + 15 - 1 = 18 = 9 x 2, which is divisible by 9, so P(1) is true. [1 mark]
Inductive hypothesis. Assume P(k) is true for some positive integer k, i.e. 4^k + 15k - 1 = 9m for some integer m, so 4^k = 9m - 15k + 1. [1 mark]
Inductive step. Consider P(k+1): 4^(k+1) + 15(k+1) - 1 = 4 x 4^k + 15k + 14. Substitute 4^k: = 4(9m - 15k + 1) + 15k + 14 = 36m - 60k + 4 + 15k + 14 = 36m - 45k + 18 = 9(4m - 5k + 2). [2 marks]
Since 4m - 5k + 2 is an integer, 4^(k+1) + 15(k+1) - 1 is divisible by 9, so P(k) true implies P(k+1) true. By the principle of mathematical induction, P(n) is true for all positive integers n. [1 mark]

2017 SACE Stage 26 marksUse mathematical induction to prove that 1/(1 x 4) + 1/(4 x 7) + ... + 1/((3n-2)(3n+1)) = n/(3n+1), where n is a positive integer.

Show worked answer →

Let P(n) be the statement that the sum equals n/(3n+1).

Base case (n = 1). Left side = 1/(1 x 4) = 1/4. Right side = 1/(3(1)+1) = 1/4. So P(1) is true. [1 mark]
Inductive hypothesis. Assume P(k): the sum to k terms = k/(3k+1). [1 mark]
Inductive step. Add the (k+1)th term 1/((3k+1)(3k+4)) to both sides:
sum = k/(3k+1) + 1/((3k+1)(3k+4)) = [k(3k+4) + 1] / ((3k+1)(3k+4)) = (3k^2 + 4k + 1)/((3k+1)(3k+4)). [2 marks]
Factorise the numerator: 3k^2 + 4k + 1 = (3k+1)(k+1), so sum = (3k+1)(k+1)/((3k+1)(3k+4)) = (k+1)/(3(k+1)+1). This is P(k+1). [1 mark]
Since P(1) holds and P(k) implies P(k+1), by induction P(n) is true for all positive integers n. [1 mark]

2018 SACE Stage 25 marksProve 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 x 1, divisible by 4, so P(1) is true. [1 mark]
Inductive hypothesis. Assume P(k) is true: 5^k - 1 = 4m for some integer m, so 5^k = 4m + 1. [1 mark]
Inductive step. Consider 5^(k+1) - 1 = 5 x 5^k - 1 = 5(4m + 1) - 1 = 20m + 5 - 1 = 20m + 4 = 4(5m + 1). [2 marks]
Since 5m + 1 is an integer, 5^(k+1) - 1 is divisible by 4, so P(k) implies P(k+1). By the principle of mathematical induction, P(n) holds for all positive integers n. [1 mark]