What is weak algebra in the step?

Aim to reach the formula with n = k + 1 exactly; factor early and simplify carefully rather than expanding blindly.

What is not stating P?

Define the proposition clearly at the start so the base case and step have something precise to verify.

SEAB Original-style practice: Prove by induction that _r=1^n r(r+1) = n(n+1)(n+2)3 for all positive integers n.

Let P(n) be the statement _r=1^n r(r+1) = n(n+1)(n+2)3. Base case n = 1: LHS = 1 × 2 = 2; RHS = 1 × 2 × 33 = 2. So P(1) holds. Inductive step: assume P(k) true, that is _r=1^k r(r+1) = k(k+1)(k+2)3. Then _r=1^k+1 r(r+1) = k(k+1)(k+2)3 + (k+1)(k+2) = (k+1)(k+2)(k3 + 1) = (k+1)(k+2)k+33 = (k+1)(k+2)(k+3)3. This is the formula with n = k + 1, so P(k) P(k+1). Since P(1) holds and P(k) P(k+1), by induction P(n) holds for all positive integers n. Markers reward a clear statement of P(n), the base case, the assumption, correct algebra to reach the k+1 form, and the concluding sentence.

SEAB Original-style practice: Prove by 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. Base case n = 1: 5^1 - 1 = 4, divisible by 4. So P(1) holds. Inductive step: assume 5^k - 1 = 4m for some integer m. Then 5^k+1 - 1 = 5 · 5^k - 1 = 5(4m + 1) - 1 = 20m + 5 - 1 = 20m + 4 = 4(5m + 1), which is divisible by 4. So P(k) P(k+1). Since P(1) holds, by induction 5^n - 1 is divisible by 4 for all positive integers n. Markers reward the base case, expressing 5^k - 1 = 4m, the manipulation extracting a factor of 4, and the conclusion.

SingaporeMathsSyllabus dot point

How does proof by mathematical induction establish a result for every positive integer?

Use the principle of mathematical induction to prove statements about sums of series, divisibility and other results indexed by the positive integers

A focused answer to the H2 Mathematics outcome on mathematical induction. The base case, the inductive step, writing a rigorous proof, and applying induction to series sums and divisibility results.

Generated by Claude Opus 4.89 min answerUpdated 2026-06-06

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 answer
Examples in context
Try this

What this dot point is asking

SEAB wants you to prove statements indexed by the positive integers using the principle of mathematical induction: establish a base case, assume the result for $n = k$ , prove it for $n = k + 1$ , and conclude. The commonest applications are sums of series and divisibility results.

The answer

The principle

To prove a statement $P(n)$ for all integers $n \geq 1$ :

Base case. Show $P(1)$ is true.
Inductive step. Assume $P(k)$ is true for some $k \geq 1$ (the inductive hypothesis), and use this to prove $P(k + 1)$ .
Conclusion. Since $P(1)$ holds and each true case forces the next, $P(n)$ holds for all $n \geq 1$ .

The image is a row of dominoes: the base case topples the first, the inductive step guarantees each topples the next, so all fall.

Structuring a series proof

For a sum, the inductive step starts from the assumed sum to $k$ terms and adds the $(k+1)$ th term. The algebra goal is to massage this into exactly the formula with $n$ replaced by $k + 1$ . Factor out common terms early to keep the working clean.

Structuring a divisibility proof

For " $\mathrm{expr}(n)$ is divisible by $d$ ", write the hypothesis as $\mathrm{expr}(k) = d m$ for some integer $m$ , then manipulate $\mathrm{expr}(k+1)$ to expose a factor of $d$ , using the hypothesis to substitute.

Writing it rigorously

State $P(n)$ explicitly, carry out the base case with both sides evaluated, label the inductive hypothesis, derive the $k+1$ case, and finish with the standard concluding sentence. Markers reward this exact scaffolding.

Worked example

Prove by induction that $\displaystyle\sum_{r=1}^{n} (2r - 1) = n^2$ for all positive integers $n$ .

Step 1: State the proposition

Let $P(n)$ be the statement $\displaystyle\sum_{r=1}^{n} (2r - 1) = n^2$ .

Step 2: Base case

For $n = 1$ : LHS $= 2(1) - 1 = 1$ ; RHS $= 1^2 = 1$ . So $P(1)$ is true.

Step 3: Inductive hypothesis

Assume $P(k)$ holds: $\displaystyle\sum_{r=1}^{k} (2r - 1) = k^2$ .

Step 4: Inductive step

Add the $(k+1)$ th term, which is $2(k+1) - 1 = 2k + 1$ :

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

This is the formula with $n = k + 1$ , so $P(k) \Rightarrow P(k + 1)$ .

Step 5: Conclusion

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

Examples in context

Example 1. Verifying a summation result. The standard result $\sum_{r=1}^{n} r = \dfrac{n(n+1)}{2}$ can be proved by induction: the step adds $k + 1$ to $\dfrac{k(k+1)}{2}$ to get $\dfrac{(k+1)(k+2)}{2}$ , confirming the closed form rather than just asserting it.

Example 2. Divisibility in number theory. Proving $n^3 - n$ is divisible by $6$ for all $n$ uses induction with the hypothesis $k^3 - k = 6m$ ; expanding $(k+1)^3 - (k+1)$ and substituting shows the result extends, a typical discrete-mathematics application.

Try this

Q1. State the three parts of a proof by mathematical induction. [2 marks]

Cue. Base case ( $P(1)$ true), inductive step ( $P(k) \Rightarrow P(k+1)$ ), conclusion (by the principle, true for all $n$ ).

Q2. In an induction proof of a sum, what do you add to the assumed sum to $k$ terms? [1 mark]

Cue. The $(k+1)$ th term of the series.

Q3. For a divisibility proof that $7^n - 1$ is divisible by $6$ , write down the inductive hypothesis. [2 marks]

Cue. Assume $7^k - 1 = 6m$ for some integer $m$ .

Exam-style practice questions

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

Original6 marksProve by induction that

\displaystyle\sum_{r=1}^{n} r(r+1) = \dfrac{n(n+1)(n+2)}{3}

for all positive integers

n

Show worked answer →

Let $P(n)$ be the statement $\sum_{r=1}^{n} r(r+1) = \dfrac{n(n+1)(n+2)}{3}$ .

Base case $n = 1$ : LHS $= 1 \times 2 = 2$ ; RHS $= \dfrac{1 \times 2 \times 3}{3} = 2$ . So $P(1)$ holds.

Inductive step: assume $P(k)$ true, that is $\sum_{r=1}^{k} r(r+1) = \dfrac{k(k+1)(k+2)}{3}$ .

Then $\sum_{r=1}^{k+1} r(r+1) = \dfrac{k(k+1)(k+2)}{3} + (k+1)(k+2) = (k+1)(k+2)\left(\dfrac{k}{3} + 1\right) = (k+1)(k+2)\dfrac{k+3}{3} = \dfrac{(k+1)(k+2)(k+3)}{3}$ .

This is the formula with $n = k + 1$ , so $P(k) \Rightarrow P(k+1)$ .

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

Markers reward a clear statement of $P(n)$ , the base case, the assumption, correct algebra to reach the $k+1$ form, and the concluding sentence.

Original5 marksProve by 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$ , divisible by $4$ . So $P(1)$ holds.

Inductive step: assume $5^k - 1 = 4m$ for some integer $m$ . Then $5^{k+1} - 1 = 5 \cdot 5^k - 1 = 5(4m + 1) - 1 = 20m + 5 - 1 = 20m + 4 = 4(5m + 1)$ , which is divisible by $4$ .

So $P(k) \Rightarrow P(k+1)$ . Since $P(1)$ holds, by induction $5^n - 1$ is divisible by $4$ for all positive integers $n$ .

Markers reward the base case, expressing $5^k - 1 = 4m$ , the manipulation extracting a factor of $4$ , and the conclusion.