Math Induction Proof: Complete Guide with Worked Examples

Mathematical induction is one of the most powerful and elegant proof techniques in mathematics — and one of the most important to master for students aiming at the Euclid Contest, the COMC, or any senior-level mathematics competition. A math induction proof allows you to prove that a statement is true for all positive integers (or all integers beyond some starting value) by proving just two things: that it is true for the first case, and that if it is true for any case k, it must also be true for the next case k + 1.

This guide covers the complete method, from the three-step structure through worked examples at increasing difficulty, common mistakes, and how math induction proof appears in competition mathematics.

What Is Mathematical Induction?

Mathematical induction is a proof technique used to prove that a statement P(n) is true for all positive integers n (or for all integers n ≥ some starting value n₀).

The logic is often compared to a domino chain:

If the first domino falls (base case), and
If every domino that falls causes the next one to fall (inductive step),
Then all dominoes will eventually fall (the statement is true for all n).

The method does not check every case individually — it proves that the truth of any one case forces the next to be true, and that the chain starts at n = 1 (or wherever the base case is set).

When to use a math induction proof:

Proving formulas for sums or series (e.g. 1 + 2 + … + n = n(n+1)/2)
Proving divisibility statements (e.g. 3ⁿ − 1 is always divisible by 2)
Proving inequalities that hold for all n
Proving properties of sequences defined recursively
Proving combinatorial identities

Many students can repeat the three steps of mathematical induction—but struggle when they’re asked to apply them in unfamiliar questions.

A free assessment shows whether your child genuinely understands proof techniques before they appear on tests and exams.

→ Get your free personalised feedback report

The Three Steps of a Math Induction Proof

Every math induction proof has exactly three parts, always in this order:

Math Induction Proof Step 1: Base Case

Prove that P(n) is true for the smallest value of n in the claim — usually n = 1, but sometimes n = 0 or n = 2 or another starting value.

The base case is a direct calculation or verification. You substitute the specific value and check that the statement holds. This is usually the shortest part of the proof.

Math Induction Proof Step 2: Inductive Hypothesis

Assume that P(k) is true for some arbitrary positive integer k ≥ 1 (or whatever the starting value is).

This is an assumption — you are not proving P(k) here, you are assuming it. State it clearly and explicitly: “Assume P(k) is true, i.e., [write out what P(k) says with k substituted].”

This assumption is what you are allowed to use in Step 3.

Math Induction Proof Step 3: Inductive Step

Using the inductive hypothesis (that P(k) is true), prove that P(k+1) must also be true.

This is the heart of the proof and the part that requires mathematical skill. The approach varies by problem type:

For sum formulas: start from the P(k) assumption, add the (k+1)th term to both sides, and manipulate algebraically to reach the P(k+1) form
For divisibility: express the (k+1) case in terms of the k case and show the divisibility follows
For inequalities: use the inductive hypothesis and algebraic manipulation to establish the inequality for k+1

Conclusion: State clearly that by the principle of mathematical induction, P(n) is true for all positive integers n (or for all n ≥ n₀, as appropriate).

Can your child remember the three steps—or explain why they work?

That’s the difference between memorising a proof and understanding one.

Take our free assessment →

Worked Examples: Math Induction Proof

Example 1 — Sum Formula (Classic, Grade 11/12 level)

Claim: For all positive integers n, $1 + 2 + 3 + \cdots + n = \frac{n(n+1)}{2}$ 1+2+3+⋯+n=2n(n+1)

Step 1 — Base Case (n = 1): LHS = 1 RHS = 1(1+1)/2 = 2/2 = 1 LHS = RHS ✓ Base case holds.

Step 2 — Inductive Hypothesis:Assume the statement is true for some k ≥ 1: $1 + 2 + 3 + \cdots + k = \frac{k(k+1)}{2}$ 1+2+3+⋯+k=2k(k+1)

Step 3 — Inductive Step:We want to prove P(k+1): that $1 + 2 + \cdots + k + (k+1) = \frac{(k+1)(k+2)}{2}$ 1+2+⋯+k+(k+1)=2(k+1)(k+2)

Starting from the left side: $1 + 2 + \cdots + k + (k+1)$ 1+2+⋯+k+(k+1) $= \frac{k(k+1)}{2} + (k+1) \quad \text{(by inductive hypothesis)}$ =2k(k+1)+(k+1)(by inductive hypothesis) $= \frac{k(k+1)}{2} + \frac{2(k+1)}{2}$ =2k(k+1)+22(k+1) $= \frac{k(k+1) + 2(k+1)}{2}$ =2k(k+1)+2(k+1) $= \frac{(k+1)(k+2)}{2}$ =2(k+1)(k+2)

This is exactly P(k+1). ✓

Conclusion: By the principle of mathematical induction, 1 + 2 + … + n = n(n+1)/2 for all positive integers n. □

Example 2 — Sum of Squares (Grade 12 / Euclid level)

Claim: For all positive integers n, $1^2 + 2^2 + 3^2 + \cdots + n^2 = \frac{n(n+1)(2n+1)}{6}$ 12+22+32+⋯+n2=6n(n+1)(2n+1)

Step 1 — Base Case (n = 1): LHS = 1² = 1 RHS = 1(2)(3)/6 = 6/6 = 1 ✓

Step 2 — Inductive Hypothesis:Assume for some k ≥ 1: $1^2 + 2^2 + \cdots + k^2 = \frac{k(k+1)(2k+1)}{6}$ 12+22+⋯+k2=6k(k+1)(2k+1)

Step 3 — Inductive Step:Want to show: $1^2 + 2^2 + \cdots + k^2 + (k+1)^2 = \frac{(k+1)(k+2)(2k+3)}{6}$ 12+22+⋯+k2+(k+1)2=6(k+1)(k+2)(2k+3)

Starting from the left: $\frac{k(k+1)(2k+1)}{6} + (k+1)^2 \quad \text{(inductive hypothesis)}$ 6k(k+1)(2k+1)+(k+1)2(inductive hypothesis) $= \frac{k(k+1)(2k+1)}{6} + \frac{6(k+1)^2}{6}$ =6k(k+1)(2k+1)+66(k+1)2 $= \frac{(k+1)[k(2k+1) + 6(k+1)]}{6}$ =6(k+1)[k(2k+1)+6(k+1)] $= \frac{(k+1)[2k^2 + k + 6k + 6]}{6}$ =6(k+1)[2k2+k+6k+6] $= \frac{(k+1)(2k^2 + 7k + 6)}{6}$ =6(k+1)(2k2+7k+6) $= \frac{(k+1)(k+2)(2k+3)}{6}$ =6(k+1)(k+2)(2k+3)

This is exactly P(k+1). ✓

Conclusion: By mathematical induction, the formula holds for all positive integers n. □

Example 3 — Divisibility Proof (Euclid/COMC level)

Claim: For all positive integers n, 7ⁿ − 1 is divisible by 6.

Step 1 — Base Case (n = 1): 7¹ − 1 = 6 = 6 × 1. Divisible by 6. ✓

Step 2 — Inductive Hypothesis: Assume 7ᵏ − 1 is divisible by 6 for some k ≥ 1. i.e., 7ᵏ − 1 = 6m for some integer m.

Step 3 — Inductive Step: Show 7^(k+1) − 1 is divisible by 6. $7^{k+1} – 1 = 7 \cdot 7^k – 1$ 7k+1−1=7⋅7k−1 $= 7 \cdot 7^k – 7 + 7 – 1$ =7⋅7k−7+7−1 $= 7(7^k – 1) + 6$ =7(7k−1)+6 $= 7(6m) + 6 \quad \text{(by inductive hypothesis, } 7^k – 1 = 6m\text{)}$ =7(6m)+6(by inductive hypothesis, 7k−1=6m) $= 6(7m) + 6$ =6(7m)+6 $= 6(7m + 1)$ =6(7m+1)

Since 7m + 1 is an integer, 7^(k+1) − 1 is divisible by 6. ✓

Conclusion: By mathematical induction, 7ⁿ − 1 is divisible by 6 for all positive integers n. □

Example 4 — Inequality Proof (COMC level)

Claim: For all integers n ≥ 4, 2ⁿ > n².

Note: The base case here is n = 4, not n = 1 (since the inequality is false for n = 1, 2, 3).

Step 1 — Base Case (n = 4): 2⁴ = 16, 4² = 16. But wait — 2⁴ = 4², not 2⁴ > 4².

Actually: 2⁴ = 16 and 4² = 16. They are equal at n = 4, so the strict inequality fails here too.

This illustrates an important point: always check the base case carefully before proceeding. If the claim as stated is false at n = 4, we need n ≥ 5.

Revised claim: For all integers n ≥ 5, 2ⁿ > n².

Step 1 — Base Case (n = 5): 2⁵ = 32, 5² = 25. 32 > 25. ✓

Step 2 — Inductive Hypothesis: Assume 2ᵏ > k² for some k ≥ 5.

Step 3 — Inductive Step: Show 2^(k+1) > (k+1)². $2^{k+1} = 2 \cdot 2^k > 2k^2 \quad \text{(by inductive hypothesis)}$ 2k+1=2⋅2k>2k2(by inductive hypothesis)

It remains to show 2k² ≥ (k+1)² = k² + 2k + 1. $2k^2 – (k^2 + 2k + 1) = k^2 – 2k – 1 = (k-1)^2 – 2$ 2k2−(k2+2k+1)=k2−2k−1=(k−1)2−2

For k ≥ 5: (k−1)² ≥ 16 > 2, so (k−1)² − 2 > 0. Therefore 2k² > (k+1)².

Combining: 2^(k+1) > 2k² > (k+1)². ✓

Conclusion: By mathematical induction, 2ⁿ > n² for all integers n ≥ 5. □

Note: Example 4 illustrates that a careful base case check is not just a formality — it sometimes reveals that the claim needs adjustment.

Example 5 — Geometric Series Formula (Euclid level)

Claim: For all positive integers n and r ≠ 1: $1 + r + r^2 + \cdots + r^n = \frac{r^{n+1} – 1}{r – 1}$ 1+r+r2+⋯+rn=r−1rn+1−1

Step 1 — Base Case (n = 1): LHS = 1 + r RHS = (r² − 1)/(r − 1) = (r+1)(r−1)/(r−1) = r + 1 ✓

Step 2 — Inductive Hypothesis:Assume for k ≥ 1: $1 + r + r^2 + \cdots + r^k = \frac{r^{k+1} – 1}{r – 1}$ 1+r+r2+⋯+rk=r−1rk+1−1

Step 3 — Inductive Step: $1 + r + \cdots + r^k + r^{k+1} = \frac{r^{k+1} – 1}{r – 1} + r^{k+1}$ 1+r+⋯+rk+rk+1=r−1rk+1−1+rk+1 $= \frac{r^{k+1} – 1 + r^{k+1}(r-1)}{r – 1}$ =r−1rk+1−1+rk+1(r−1) $= \frac{r^{k+1} – 1 + r^{k+2} – r^{k+1}}{r – 1}$ =r−1rk+1−1+rk+2−rk+1 $= \frac{r^{k+2} – 1}{r – 1}$ =r−1rk+2−1

This is P(k+1). ✓ □

Understanding an example is very different from writing a proof independently.

Our free assessment identifies exactly where students struggle—whether that’s setting up the induction, handling algebra, or completing the inductive step.

→ Get your free feedback report

Strong Induction

Strong induction (also called complete induction) is a variant where the inductive hypothesis assumes P(j) is true for all j with 1 ≤ j ≤ k, rather than just P(k).

When to use strong induction:

When the (k+1) case depends on several earlier cases, not just the immediately preceding one
Fibonacci sequences and similar recursive definitions
Proofs involving the Fundamental Theorem of Arithmetic

Example structure (strong induction):

Base case: Verify P(1) (and sometimes P(2) if the step requires two prior cases).

Inductive hypothesis: Assume P(j) is true for all 1 ≤ j ≤ k.

Inductive step: Prove P(k+1) using any of P(1), P(2), …, P(k) as needed.

Strong induction is logically equivalent to ordinary induction — a statement provable by one method is provable by the other. The choice of which to use depends on which is more natural for the specific problem.

Common Mistakes in Math Induction Proof

Mistake 1: Skipping the base case or treating it as unimportant. The base case is not a formality — it is what anchors the chain. A proof that shows P(k) → P(k+1) without a valid base case proves nothing. There exist mathematical statements that satisfy the inductive step for all k but are false for every specific n (because the base case fails).

Mistake 2: Assuming what you are trying to prove. In the inductive step, students sometimes write the conclusion they want and work backwards — which is circular reasoning, not a proof. Always start from P(k) (which you are allowed to assume) and derive P(k+1) (which you must prove).

Mistake 3: Using P(k+1) in the inductive step before proving it. A variant of the above. The inductive hypothesis allows you to use P(k). You cannot use P(k+1) — that is what you are trying to establish.

Mistake 4: Not stating the inductive hypothesis clearly. Write out explicitly what P(k) says with k substituted. Vague statements lead to vague proofs. Markers at the Euclid and COMC level expect explicit, clear hypothesis statements.

Mistake 5: Wrong base case for inequality proofs. As shown in Example 4: always verify the base case before writing the proof. If the stated starting value makes the claim false, either the claim is wrong or the starting value needs adjustment. Catching this before writing saves significant time on competitions.

Mistake 6: Incomplete algebraic manipulation in the inductive step. The most common place to lose marks on a competition math induction proof — the algebraic steps from P(k) to P(k+1) need to be complete and clearly laid out. Skipping steps or writing “…and this simplifies to P(k+1)” without showing the algebra will not earn full marks.

Math Induction Proof in Competition Mathematics

Mathematical induction appears at multiple levels of the Canadian competition mathematics circuit.

Euclid Contest (CEMC, Grade 12) Induction is a legitimate and effective proof technique for Part C questions on the Euclid. Questions involving sum formulas, divisibility patterns, or recursive sequences are natural induction candidates. The Euclid rewards complete, clearly written proofs — a well-structured math induction proof with all three steps explicitly stated earns more partial credit than a clever but incomplete argument. See our Euclid math contest guide.

COMC (Canadian Open Mathematics Competition) Part C of the COMC regularly includes problems where induction is the intended proof method — particularly divisibility claims and sum identities involving all positive integers. Strong induction appears occasionally for problems involving recursive structures. See our COMC math contest guide.

General competition strategy for induction:

Identify the claim and whether it involves “all positive integers” or “all integers n ≥ k” — this determines your base case
Write the three steps in labelled sections: Base Case, Inductive Hypothesis, Inductive Step
Show all algebraic steps — competition markers award partial credit step by step
State the conclusion explicitly: “Therefore by mathematical induction…”

For the broader proof technique landscape at competition level, see our proof by contradiction guide.

Practice Problems

Work through these before checking the answers.

Set A — Sum formulas

Prove by induction: 2 + 4 + 6 + … + 2n = n(n+1)
Prove by induction: 1 + 3 + 5 + … + (2n−1) = n²
Prove by induction: 1² + 2² + … + n² = n(n+1)(2n+1)/6 (follow Example 2)

Set B — Divisibility

Prove by induction: 4ⁿ − 1 is divisible by 3 for all n ≥ 1
Prove by induction: n³ − n is divisible by 6 for all n ≥ 1
Prove by induction: 5ⁿ − 1 is divisible by 4 for all n ≥ 1

Set C — Inequalities and mixed

Prove by induction: 2ⁿ ≥ n + 1 for all n ≥ 1
Prove by induction: n! ≥ 2^(n−1) for all n ≥ 1
Prove by induction: the sum 1/(1×2) + 1/(2×3) + … + 1/(n(n+1)) = n/(n+1)

Proof outlines (Set A, Q1 — full proof):

Claim: 2 + 4 + 6 + … + 2n = n(n+1)

Base case (n=1): 2(1) = 2; 1(2) = 2. ✓

Inductive hypothesis: Assume 2 + 4 + … + 2k = k(k+1).

Inductive step: Show 2 + 4 + … + 2k + 2(k+1) = (k+1)(k+2).

LHS = k(k+1) + 2(k+1) = (k+1)(k+2). ✓ □

For problems 2–9, apply the same three-step structure. The algebraic manipulation in the inductive step is the key skill to develop.

Frequently Asked Questions

What is a math induction proof? Mathematical induction is a proof technique for showing a statement P(n) is true for all positive integers n. It works by proving two things: (1) the base case — P(1) is true; and (2) the inductive step — if P(k) is true for some k, then P(k+1) is also true. Together these establish P(n) for all n.

What are the three steps of mathematical induction? Base case (verify P(n₀) directly), inductive hypothesis (assume P(k) is true), inductive step (prove P(k+1) follows from P(k)). Always conclude by stating that the result holds for all n by the principle of mathematical induction.

When should I use strong induction instead of regular induction? When the proof of P(k+1) requires knowledge of more than just P(k) — for example, when it requires P(k−1) or P(k−2) as well. Strong induction assumes all previous cases are true, giving more to work with in the inductive step.

How is mathematical induction different from assuming what you want to prove? The inductive hypothesis assumes P(k) — a specific individual case — is true. This is a legitimate assumption in the chain of logic. You are not assuming the conclusion (that P(n) is true for all n) — you are building that conclusion step by step. The base case ensures the chain has a valid starting point.

Does mathematical induction appear on the Euclid Contest? Yes. The Euclid Part C questions are full-solution proofs where induction is a legitimate and often effective technique — particularly for sum formulas, divisibility proofs, and sequence properties. A clearly written three-step math induction proof with full algebraic working is one of the strongest ways to earn full marks on these questions.

What is the most common mistake in a math induction proof? Circular reasoning in the inductive step — using P(k+1) to prove P(k+1). The inductive step must start from P(k) (assumed true) and derive P(k+1) through logical steps. Any argument that begins by assuming the conclusion is not a valid proof.

Mathematical induction is a Part C skill. Build it before the contest — not during it.

Mathematical induction becomes much easier when students understand the reasoning behind each step—not just the structure.

In a free online trial lesson, one of our experienced teachers will show your child how to approach induction proofs confidently and avoid the mistakes that cost marks on MHF4U assessments.

→ Book your free trial lesson

Mathematical Induction: A Complete Guide with Worked Examples