Proof by induction

Higher Level

Each domino is a value of n. Choose what you have proved and watch how far the chain gets.

ready

Base case and inductive step Inductive step only, no base case Base case, but the step fails at k = 6

0values proved

nothing yetverdict

Press topple and see how far it gets.

The structure, which never changes

1. Base case. Show the statement is true for the smallest n, usually 1. Show it, do not assert it.

2. Assumption. Assume it is true for n = k. Write out exactly what that gives you, because you will need it.

3. Inductive step. Prove it then holds for n = k + 1, using the assumption somewhere. If you never use it, you have not done induction.

4. Conclusion. State it: true for n = 1, and true for k + 1 whenever true for k, so true for all n by induction.

A worked example

Prove 1 + 2 + … + n = n(n + 1)2.

n = 1→ LHS = 1, RHS = 1(2)2 = 1 ✓ assume 1 + … + k = k(k + 1)2 then k + 1= k(k + 1)2 + (k + 1) factorise= (k + 1)k + 22 which is= (k + 1)(k + 2)2 ■

That last line is the formula with k + 1 in place of n. Writing down what you are aiming for before you start the step turns the algebra into a target rather than a wander.

Divisibility works the same way

Prove 9ⁿ − 1 is divisible by 8. Base: 9 − 1 = 8 ✓. Assume 9^k − 1 = 8m. Then:

9^k+1 − 1= 9(9^k) − 1 use the assumption= 9(8m + 1) − 1 = 72m + 8 = 8(9m + 1) ■

Your turn

1. For 1 + 2 + … + n = n(n+1)/2, give the value of the right-hand side at n = 10.

2. Find 9³ − 1, then divide it by 8.

3. A proof shows the step works for every k but never checks n = 1. It has proved:

The statement for all n. Nothing. The chain has nothing to start it. The statement for all n greater than 1. That the statement is false.

Where the marks go

A base case actually evaluated on both sides, not asserted.

The assumption used explicitly in the step. Examiners look for the moment you substitute it in; a step that never uses it is not induction.

A closing statement naming both halves. It is a mark, and it is the one most often dropped.

Want a verdict on your own draft?

These pages are free and stay free, but they are general and your IA is not. Send me your research question, or whatever exists so far, and I will tell you in writing whether the topic has a ceiling on it, where the marks are going, and what to change first. That costs nothing and it comes back within 24 hours.

Written by a serving IB Diploma and Career-related Programme Coordinator and Head of Mathematics, who reads internal assessments across every subject group every year. If you then want the whole draft reviewed properly against all five criteria, that is the paid one, and it is refunded if it does not name at least three specific things to fix.

Get a free verdict Full written review, $99

I never write any part of it. Not a sentence, not a calculation, not your data. Under 18: a parent buys this and the thread is with them. I do not work with students at my own school.