Proof by mathematical induction

IB Mathematics Analysis and Approaches HL· Unit 1: Number and Algebra, Topic 1.12· 15 min read

1. The Principle of Mathematical Induction★★☆☆☆⏱ 5 min

Mathematical induction is used to prove statements that claim to be true for all integers $n$ greater than or equal to some starting value. It works like a chain of dominoes: if the first domino falls, and every falling domino knocks over the next, all dominoes will fall.

📘 Definition

Principle of Mathematical Induction

To prove a statement $P (n)$ is true for all integers $n \geq n_{0}$ : 1. Prove $P (n_{0})$ is true (base case). 2. Assume $P (k)$ is true for some arbitrary $k \geq n_{0}$ (inductive hypothesis). 3. Prove $P (k + 1)$ is true (inductive step). 4. Conclude $P (n)$ is true for all $n \geq n_{0}$ .

Example:

Used to prove sum formulas, divisibility and inequalities

📐 Worked Example

Prove that the sum of the first $n$ positive integers is $\frac{n ( n + 1 )}{2}$ for all $n \in N$

1
Step 1: Define the statement $P (n)$ :
2
$P(n): 1 + 2 + 3 + ... + n = \frac{n(n+1)}{2}$
3
Step 2: Base case $n = 1$ :
4
Left hand side (LHS) = $1$ , Right hand side (RHS) = $\frac{1 ( 1 + 1 )}{2} = 1$ . LHS = RHS, so $P (1)$ is true.
5
Step 3: Inductive hypothesis: Assume $P (k)$ is true for some positive integer $k$ :
6
$1 + 2 + ... + k = \frac{k(k+1)}{2}$
7
Step 4: Inductive step: Prove $P (k + 1)$ is true:
8
LHS of $P (k + 1)$ = $1 + 2 + ... + k + (k + 1)$
9
$= \frac{k(k+1)}{2} + (k+1) = (k+1)\left(\frac{k}{2} + 1\right) = \frac{(k+1)(k+2)}{2}$
10
This equals the RHS of $P (k + 1)$ , so $P (k + 1)$ is true.
11
Step 5: Conclusion: Since $P (1)$ is true, and $P (k)$ true implies $P (k + 1)$ true, by induction $P (n)$ is true for all $n \in N$ .

Exam tip:

Always write the final conclusion sentence, it is worth a separate mark in most mark schemes.

2. Induction for Divisibility Proofs★★★☆☆⏱ 6 min

Divisibility proofs are one of the most common induction questions in IB exams. The key difference from sum proofs is that you need to factor out the divisor from the expression for $n = k + 1$ , using the inductive hypothesis.

📐 Worked Example

Prove that $n^{3} - n$ is divisible by 3 for all $n \in N$

1
Step 1: Define $P (n) : 3 ∣ (n^{3} - n)$
2
Step 2: Base case $n = 1$ : $1^{3} - 1 = 0 = 3 \times 0$ , so $3$ divides $0$ , hence $P (1)$ is true.
3
Step 3: Inductive hypothesis: Assume $P (k)$ is true, so $k^{3} - k = 3 m$ for some integer $m$ .
4
Step 4: Prove $P (k + 1)$ : Expand $(k + 1)^{3} - (k + 1)$ :
5
$k^3 + 3k^2 + 3k + 1 - k - 1 = (k^3 - k) + 3k^2 + 3k$
6
Substitute from the inductive hypothesis:
7
$= 3m + 3k^2 + 3k = 3(m + k^2 + k)$
8
Since $m$ and $k$ are integers, $m + k^{2} + k$ is an integer, so $3$ divides $(k + 1)^{3} - (k + 1)$ , hence $P (k + 1)$ is true.
9
Step 5: Conclusion: By induction, $P (n)$ is true for all $n \in N$ .

Exam tip:

Explicitly state that the remaining factor after factoring out the divisor is an integer to earn full marks.

3. Induction for Inequalities★★★★☆⏱ 6 min

Proving inequalities by induction often requires extra algebraic manipulation to get from the inductive hypothesis to the required result for $n = k + 1$ . A common trick is to simplify the inequality to show the difference between the two sides is positive.

📐 Worked Example

Prove that $2^{n} > n^{2}$ for all integers $n \geq 5$

1
Step 1: Define $P (n) : 2^{n} > n^{2}$ for $n \geq 5$
2
Step 2: Base case $n = 5$ : LHS = $2^{5} = 32$ , RHS = $5^{2} = 25$ . $32 > 25$ , so $P (5)$ is true.
3
Step 3: Inductive hypothesis: Assume $P (k)$ is true for $k \geq 5$ , so $2^{k} > k^{2}$ .
4
Step 4: Prove $P (k + 1)$ : $2^{k + 1} = 2 \times 2^{k} > 2 k^{2}$ by the inductive hypothesis.
5
We need to show $2 k^{2} > (k + 1)^{2} = k^{2} + 2 k + 1$ , which simplifies to showing $k^{2} - 2 k - 1 > 0$ .
6
$k^2 - 2k - 1 = (k-1)^2 - 2$
7
For $k \geq 5$ , $(k - 1)^{2} \geq 16$ , so $(k - 1)^{2} - 2 \geq 14 > 0$ , so the inequality holds.
8
Hence $2^{k + 1} > 2 k^{2} > (k + 1)^{2}$ , so $P (k + 1)$ is true.
9
Step 5: Conclusion: By induction, $P (n)$ is true for all $n \geq 5$ .

Exam tip:

Always check the starting value of $n$ : it is not always $n = 1$ , and a wrong base case invalidates the entire proof.

4. Common Pitfalls

Wrong move:

Forgetting to explicitly state the inductive hypothesis

Why:

Examiners require this to confirm you understand the structure of induction, you will lose a method mark.

Correct move:

Always write: "Assume the statement is true for $n = k$ , that is [restate the full statement for $n = k$ ]".

Wrong move:

Assuming the statement is true for $n = k + 1$ in the inductive step

Why:

This is circular reasoning: you assume the result you are trying to prove, so the proof is invalid.

Correct move:

Only assume the statement holds for $n = k$ , then manipulate the expression for $n = k + 1$ to prove it is true.

Wrong move:

Testing the wrong base case for statements starting at $n \neq = 1$

Why:

The entire induction chain starts at the base case, so a wrong starting point makes the proof incorrect.

Correct move:

Always read the question carefully to find the starting value of $n$ , and test that value first.

Wrong move:

Stopping after the inductive step without writing a conclusion

Why:

Most IB mark schemes award a separate mark for the final conclusion sentence.

Correct move:

Always end with: "By the principle of mathematical induction, the statement is true for all integers $n \geq n_{0}$ ".

5. Quick Reference Cheatsheet

Step Name	Required Action
Base Case	Test the statement for the smallest $n$ given
Inductive Hypothesis	State assumption: statement true for $n = k$
Inductive Step	Prove statement true for $n = k + 1$ using assumption
Conclusion	Write the standard concluding sentence

6. Frequently Asked

Do I need to write the inductive hypothesis explicitly?

Yes, examiners require you to clearly state your assumption for $n = k$ to award the method mark. Failing to state it loses marks.

Is induction accepted as a valid proof in IB exams?

Yes, as long as all three steps are clearly completed and the conclusion is stated, full marks are awarded for induction proofs.

When this came up on past exams

AI-estimated based on syllabus patterns — cross-check with official past papers for accuracy. Use only as revision-focus signals.

2021 · 1
Divisibility proof by induction
2022 · 2
Sum of sequence proof by induction
2023 · 1
Inequality proof by induction

Going deeper

syllabusOfficial IB Math AA HL SyllabusLatest official syllabus document for reference

What's Next

Proof by mathematical induction is a core proof technique that forms the foundation of many results in discrete mathematics, sequences and number theory. You will use it later to confirm properties of recurrence relations, matrix powers, and combinatorial identities. Mastering the clear step-by-step structure now will help you earn full marks on these questions when they appear in exams, since induction questions are often straightforward method marks if you follow the process correctly, and make up a small but consistent portion of exam paper marks.