What is wrong base case?

If the statement only holds from n = 5, verifying n = 1 is pointless. Start at the correct n_0.

What is sloppy algebra in the step?

Factorising the k+1 expression to match the target form is where marks are won or lost. Show the manipulation in full.

NESA 2024 HSC-style practice: Use mathematical induction to prove that C(2n, n) = 5, where C(2n, n) = (2n)!/(n! n!).

Let P(n) be the statement C(2n, n) = 5. Consider C(2k + 2, k + 1) = (2k + 2)!/((k + 1)! (k + 1)!). Relate it to C(2k, k): (2k + 2)! = (2k + 2)(2k + 1)(2k)! and (k + 1)! = (k + 1) k!, so C(2k + 2, k + 1) = [(2k + 2)(2k + 1)] / [(k + 1)^2] . C(2k, k) = [2(2k + 1)/(k + 1)] . C(2k, k). Now 2(2k + 1)/(k + 1) = (4k + 2)/(k + 1) = 5. Mark notes: 1 mark for the base case n = 5, 1 mark for expressing C(2k+2, k+1) in terms of C(2k, k), 1 mark for bounding the ratio by 4 and completing the step.

NSWMaths Extension 2Syllabus dot point

How does mathematical induction prove statements about all positive integers, including inequalities and divisibility results?

Prove results involving sums, divisibility and inequalities for all integers using the principle of mathematical induction

A focused answer to the HSC Maths Extension 2 dot point on further mathematical induction. The base case, induction hypothesis and inductive step, applied to series, divisibility and inequalities with rigorous worked examples.

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

Jump to a section

What this dot point is asking
The structure of an induction proof
Induction on a series
Induction on divisibility
Induction on inequalities

What this dot point is asking

NESA wants you to prove statements that hold for all integers from some starting value using mathematical induction. Extension 2 pushes beyond simple series sums to harder divisibility results, inequalities, and cases requiring careful algebraic manipulation in the inductive step.

The structure of an induction proof

To prove that $P(n)$ holds for all integers $n \ge n_0$ :

Base case: verify $P(n_0)$ directly.
Inductive hypothesis: assume $P(k)$ is true for some arbitrary integer $k \ge n_0$ .
Inductive step: using the hypothesis, prove $P(k+1)$ .
Conclusion: by the principle of mathematical induction, $P(n)$ holds for all integers $n \ge n_0$ .

The logic is a chain. The base case starts it; the inductive step lets each true statement force the next, so truth propagates from $n_0$ to every later integer.

Induction on a series

Prove that $\displaystyle\sum_{r=1}^{n} r^2 = \frac{n(n+1)(2n+1)}{6}$ for all integers $n \ge 1$ .

Base case ( $n = 1$ ): the left side is $1^2 = 1$ ; the right side is $\dfrac{1 \cdot 2 \cdot 3}{6} = 1$ . Equal, so $P(1)$ holds.

Inductive step: assume $\displaystyle\sum_{r=1}^{k} r^2 = \dfrac{k(k+1)(2k+1)}{6}$ . Then

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

The bracket is $2k^2 + 7k + 6 = (k+2)(2k+3)$ , so

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

which is exactly the formula with $n = k+1$ . The result follows by induction.

Induction on divisibility

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

Base case ( $n = 1$ ): $7^1 - 1 = 6$ , which is divisible by $6$ .

Inductive step: assume $7^k - 1 = 6M$ for some integer $M$ , so $7^k = 6M + 1$ . Then

7^{k+1} - 1 = 7 \cdot 7^k - 1 = 7(6M + 1) - 1 = 42M + 7 - 1 = 42M + 6 = 6(7M + 1).

Since $7M + 1$ is an integer, $7^{k+1} - 1$ is divisible by $6$ . The result follows by induction.

Induction on inequalities

Prove that $2^n > n^2$ for all integers $n \ge 5$ .

Base case ( $n = 5$ ): $2^5 = 32$ and $5^2 = 25$ , and $32 > 25$ , so $P(5)$ holds.

Inductive step: assume $2^k > k^2$ for some $k \ge 5$ . Then $2^{k+1} = 2 \cdot 2^k > 2k^2$ . It suffices to show $2k^2 \ge (k+1)^2$ for $k \ge 5$ . Now

2k^2 - (k+1)^2 = 2k^2 - k^2 - 2k - 1 = k^2 - 2k - 1 = (k-1)^2 - 2,

and for $k \ge 5$ this is $(k-1)^2 - 2 \ge 16 - 2 = 14 > 0$ . Hence $2^{k+1} > 2k^2 \ge (k+1)^2$ , completing the step.

Exam-style practice questions

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

2021 HSC3 marksProve by mathematical induction that n! > 2^n, for integers n >= 9.

Show worked answer →

Let P(n) be the statement n! > 2^n.

Base case n = 9: LHS = 9! = 362880 and RHS = 2^9 = 512. Since 362880 > 512, P(9) is true.

Inductive step: assume P(k) holds for some integer k >= 9, that is k! > 2^k. Show P(k + 1), i.e. (k + 1)! > 2^(k + 1).

(k + 1)! = (k + 1) . k! > (k + 1) . 2^k (using the assumption k! > 2^k).

Since k >= 9, we have k + 1 >= 10 > 2, so (k + 1) . 2^k > 2 . 2^k = 2^(k + 1).

Therefore (k + 1)! > 2^(k + 1), so P(k + 1) is true.

By the principle of mathematical induction, n! > 2^n for all integers n >= 9.

Mark notes: 1 mark for verifying the base case n = 9, 1 mark for using the assumption to write (k + 1)! > (k + 1) 2^k, 1 mark for completing the inequality and stating the conclusion.

2023 HSC4 marks(i) Show that k^2 - 2k - 3 >= 0 for k >= 3. (ii) Hence, or otherwise, use mathematical induction to prove that 2^n >= n^2 - 2, for all integers n >= 3.

Show worked answer →

Part (i). Factor: k^2 - 2k - 3 = (k - 3)(k + 1). For k >= 3, both factors are non-negative, so (k - 3)(k + 1) >= 0. Hence k^2 - 2k - 3 >= 0 for k >= 3.

Part (ii). Let P(n) be 2^n >= n^2 - 2.

Base case n = 3: LHS = 2^3 = 8, RHS = 3^2 - 2 = 7. Since 8 >= 7, P(3) is true.

Inductive step: assume 2^k >= k^2 - 2 for some k >= 3. Then

2^(k + 1) = 2 . 2^k >= 2(k^2 - 2) = 2k^2 - 4.

We want 2^(k + 1) >= (k + 1)^2 - 2 = k^2 + 2k - 1. Compare:
2k^2 - 4 - (k^2 + 2k - 1) = k^2 - 2k - 3 >= 0 for k >= 3 by part (i).

So 2k^2 - 4 >= k^2 + 2k - 1, giving 2^(k + 1) >= (k + 1)^2 - 2. Thus P(k + 1) holds.

By induction, 2^n >= n^2 - 2 for all integers n >= 3.

Mark notes: 1 mark for part (i); then 1 mark for the base case, 1 mark for using the assumption to get 2^(k+1) >= 2k^2 - 4, 1 mark for invoking part (i) to finish the inductive step.

2024 HSC3 marksUse mathematical induction to prove that C(2n, n) < 2^(2n - 2), for all integers n >= 5, where C(2n, n) = (2n)!/(n! n!).

Show worked answer →

Let P(n) be the statement C(2n, n) < 2^(2n - 2).

Base case n = 5: C(10, 5) = 252 and 2^(2(5) - 2) = 2^8 = 256. Since 252 < 256, P(5) is true.

Inductive step: assume C(2k, k) < 2^(2k - 2) for some k >= 5. Consider

C(2k + 2, k + 1) = (2k + 2)!/((k + 1)! (k + 1)!).

Relate it to C(2k, k): (2k + 2)! = (2k + 2)(2k + 1)(2k)! and (k + 1)! = (k + 1) k!, so

C(2k + 2, k + 1) = [(2k + 2)(2k + 1)] / [(k + 1)^2] . C(2k, k) = [2(2k + 1)/(k + 1)] . C(2k, k).

Now 2(2k + 1)/(k + 1) = (4k + 2)/(k + 1) < 4 because 4k + 2 < 4k + 4. Using the assumption:

C(2k + 2, k + 1) < 4 . C(2k, k) < 4 . 2^(2k - 2) = 2^2 . 2^(2k - 2) = 2^(2k) = 2^(2(k + 1) - 2).

So P(k + 1) holds. By induction, C(2n, n) < 2^(2n - 2) for all integers n >= 5.

Mark notes: 1 mark for the base case n = 5, 1 mark for expressing C(2k+2, k+1) in terms of C(2k, k), 1 mark for bounding the ratio by 4 and completing the step.