IB Maths AA HL Topic 1 — Number & Algebra Paper 1 & 2 HL only ~10 min read

Proof by Induction

Induction is the standard way to prove a result that depends on a positive integer n — sums, divisibility claims, derivative patterns. The trick is that you don’t have to handle every n directly. You show the result is true for n = 1, then show that if it’s true for some n = k, it must also be true for n = k + 1. Those two pieces — combined — force the result to hold for every positive integer. Once you’ve memorised the four-step template, induction is one of the most reliable mark-grabbers on Paper 1.

📘 What you need to know

Induction proves a statement P(n) is true for all n ∈ ℤ⁺ using a fixed four-step structure.
Step 1 — Basic step: show P(1) is true (substitute n = 1 into both sides of the claim).
Step 2 — Assumption: assume P(k) is true for some integer k.
Step 3 — Inductive step: use the assumption to prove P(k + 1) follows.
Step 4 — Conclusion: end with the standard two-sentence wrap-up. Always use the same wording.
The two main types are series (sums equal a closed form) and divisibility (an expression is divisible by a fixed number). The structure is identical; only Step 3’s algebra differs.

The domino picture

The clearest way to picture induction is as a row of dominoes. To knock them all down, you only need two things: knock the first one over, and arrange them so each falling domino topples the next. You don’t need to push every domino individually.

Why two pieces are enough to fell every domino

“Push the first domino” is the basic step. “Each domino topples its neighbour” is the inductive step. Together they guarantee that every domino down the line falls — even though you only physically pushed one.

The four-step template

Every induction proof in IB exams follows the same four-step shape. Memorise it once, then drop the right algebra into each box.

Basic step

Show P(1) holds. Substitute n = 1 into both sides.

Assumption

Assume P(k) is true for some integer k.

Inductive step

Use the assumption to derive P(k + 1).

Conclusion

Standard two-sentence finish — see below.

The standard conclusion (memorise word-for-word) “If the result is true for n = k, then it is true for n = k + 1.
Since it is true for n = 1, by induction the result is true for all n ∈ ℤ⁺.”

The conclusion is worth a mark on its own. Don’t paraphrase it — just write the same two sentences every time. Examiners look for these exact phrases: “true for n = k implies true for n = k + 1″, and “true for n = 1, so true for all n ∈ ℤ⁺“.

Type 1 — Induction with a series (sum equals a formula)

The most common induction question gives you a sum on the left and a closed-form expression on the right, and asks you to prove they’re equal for all positive integers.

The shape of a series claim Σ_r=1ⁿ f(r) = g(n)

Step 3 — the inductive step trick

The key move in the inductive step is to split off the last term from the sum and use the assumption on the rest:

Σ_r=1^k+1 f(r) = Σ_r=1^k f(r) + f(k + 1)

Now you replace the first sum with the formula g(k) (that’s the assumption), then add f(k + 1) and simplify. The target is to make the whole thing match g(k + 1) — what you’d get from the right-hand side at n = k + 1.

Algebra to expect: expanding brackets, then factorising out a common factor (often k + 1 or a constant from the RHS coefficient). The factorise step is what links the work back to the target form.

Type 2 — Induction with divisibility

The other main type asks you to prove that an expression like 5ⁿ − 1, or n³ + 2n, is divisible by some fixed integer (often 3, 4, or 5).

Step 3 — the inductive step trick

“Divisible by 3” is just the same as “= 3m for some integer m“. So in Step 2 you write the assumption in that form. Then in Step 3, substitute n = k + 1 into the expression, use index laws like a^{k + 1} = a · a^k to spot the assumption, and rearrange until you can factor out the divisor (3, 4, etc.).

The pattern to chase Show: P(k + 1) = (divisor) × (some integer)

For divisibility by 3, your goal is to write the result as 3 × (integer). For divisibility by 5, write 5 × (integer). The key sentence at the end is “…which is a multiple of [divisor], so P(k + 1) is true.”

Worked examples

WE 1

Prove a sum formula by induction

Prove by induction that Σ_r=1ⁿ r = n(n + 1)2 for all n ∈ ℤ⁺.

STEP 1 — Basic step (n = 1) LHS = 1, RHS = 1(2)/2 = 1 ✓ STEP 2 — Assumption assume Σ_r=1^k r = k(k+1)/2 holds for some k STEP 3 — Inductive step (n = k + 1) Σ_r=1^k+1 r = Σ_r=1^k r + (k+1) = k(k+1)/2 + (k+1) (using assumption) = (k+1)[k/2 + 1] = (k+1)(k+2)/2 RHS at n = k+1: (k+1)(k+2)/2 ✓ match STEP 4 — Conclusion If true for n = k, then true for n = k+1. Since true for n = 1, by induction the result is true for all n ∈ ℤ⁺.

WE 2

Sum of the first n odd numbers

Prove by induction that Σ_r=1ⁿ (2r − 1) = n² for all n ∈ ℤ⁺.

STEP 1 — Basic step (n = 1) LHS = 2(1) − 1 = 1, RHS = 1² = 1 ✓ STEP 2 — Assumption assume Σ_r=1^k (2r − 1) = k² STEP 3 — Inductive step Σ_r=1^k+1 (2r − 1) = Σ_r=1^k (2r − 1) + [2(k+1) − 1] = k² + (2k + 1) (using assumption) = k² + 2k + 1 = (k + 1)² RHS at n = k+1: (k+1)² ✓ STEP 4 — Conclusion If true for n = k, then true for n = k+1. Since true for n = 1, by induction the result is true for all n ∈ ℤ⁺. spotting that k² + 2k + 1 = (k+1)² is the whole game here

WE 3

Sum of cubes

Prove by induction that Σ_r=1ⁿ r³ = n²(n + 1)²4 for all n ∈ ℤ⁺.

STEP 1 — n = 1 LHS = 1, RHS = 1·4/4 = 1 ✓ STEP 2 — Assumption assume Σ_r=1^k r³ = k²(k+1)²/4 STEP 3 — Inductive step Σ_r=1^k+1 r³ = k²(k+1)²/4 + (k+1)³ = (k+1)²[k²/4 + (k+1)] (factor out (k+1)²) = (k+1)²[k² + 4(k+1)]/4 = (k+1)²(k² + 4k + 4)/4 = (k+1)²(k+2)²/4 RHS at n = k+1: (k+1)²(k+2)²/4 ✓ STEP 4 — Conclusion If true for n = k, then true for n = k+1. Since true for n = 1, by induction the result is true for all n ∈ ℤ⁺. factoring out (k+1)² early keeps the algebra tidy

WE 4

Prove a divisibility result

Prove by induction that 7ⁿ − 1 is divisible by 6 for all n ∈ ℤ⁺.

STEP 1 — n = 1 7¹ − 1 = 6, divisible by 6 ✓ STEP 2 — Assumption assume 7^k − 1 = 6m for some m ∈ ℤ so 7^k = 6m + 1 STEP 3 — Inductive step (n = k + 1) 7^k+1 − 1 = 7 · 7^k − 1 = 7(6m + 1) − 1 (using assumption) = 42m + 7 − 1 = 42m + 6 = 6(7m + 1) since 7m + 1 ∈ ℤ, this is a multiple of 6 ✓ STEP 4 — Conclusion If true for n = k, then true for n = k+1. Since true for n = 1, by induction the result is true for all n ∈ ℤ⁺. 7^(k+1) = 7·7^k is the key index-law step — lets you slot in the assumption

WE 5

Divisibility by 5

Prove by induction that 6ⁿ − 1 is divisible by 5 for all n ∈ ℤ⁺.

STEP 1 — n = 1 6 − 1 = 5, divisible by 5 ✓ STEP 2 — Assumption assume 6^k − 1 = 5m, so 6^k = 5m + 1 STEP 3 — Inductive step 6^k+1 − 1 = 6 · 6^k − 1 = 6(5m + 1) − 1 = 30m + 6 − 1 = 30m + 5 = 5(6m + 1) since 6m + 1 ∈ ℤ, this is a multiple of 5 ✓ STEP 4 — Conclusion If true for n = k, then true for n = k+1. Since true for n = 1, by induction the result is true for all n ∈ ℤ⁺.

💡 Top tips

Always write all four step headings. “Basic step”, “Assumption”, “Inductive step”, “Conclusion”. Examiners scan for these.
Memorise the conclusion sentences word-for-word. Don’t reword them.
For sums: peel off the last term as f(k + 1) and use the assumption on the remaining k terms.
For divisibility: write the assumption as “= 3m“ (or 5m, 6m, etc.). Then use a^k+1 = a · a^k to spot it.
When factorising in Step 3, look for (k + 1) as a common factor. It’s almost always there in series-type questions.
Once you’ve simplified your Step 3, quickly substitute n = k + 1 into the original RHS and check the two match.
If the question gives a starting value other than n = 1 (rare but possible), check that one in the basic step instead.

⚠ Common mistakes

Skipping the basic step. Without P(1), the whole induction collapses — you need to push the first domino.
Writing “let n = k + 1” without using the assumption. Step 3 must use what you assumed in Step 2 — that’s the entire point.
Treating the assumption as something to prove. You assume P(k) to derive P(k + 1). Don’t try to prove the assumption itself.
Incomplete or paraphrased conclusion. Use the standard two sentences. Skipping “true for all n ∈ ℤ⁺” loses a mark.
Algebra errors when expanding (k + 1)², (k + 1)³, etc. Double-check expansions in Step 3 — sign and coefficient errors here destroy the proof.
Forgetting “since (bracket) is an integer” in divisibility proofs. The bracket inside the divisor multiplication must be confirmed as an integer.
Using the wrong index law for the inductive step. 7^{k + 1} is 7 · 7^k, not (7^k)².

Induction looks intimidating the first time, but it’s heavily rewarded by IB examiners precisely because the structure is so rigid. Drill the four steps once, work through three or four problems, and you’ll have it for life. The conclusion sentences are free marks — never skip them.

Need help with Proof by Induction?

Get 1-on-1 help from an IB examiner who knows exactly what Paper 1 & 2 are looking for.

Book Free Session →

Proof by Induction

📘 What you need to know

The domino picture

The four-step template

Type 1 — Induction with a series (sum equals a formula)

Step 3 — the inductive step trick

Type 2 — Induction with divisibility

Step 3 — the inductive step trick

Worked examples

💡 Top tips

⚠ Common mistakes

Need help with Proof by Induction?

Quick Links

Contact us

Follow us