Chapter 2 · Sequences · Concept 5
2-23 Mathematical Induction for Proving Equalities
1 + 2 + 3 + … + n = ½n(n+1). You can check it for n = 1, for n = 100, for a million. But a sequence has infinitely many terms, and no amount of checking reaches them all. There is a way — and it takes exactly two steps.
Guiding question
How can you prove something for every whole number at once?
Learning outcome. Apply the principle of mathematical induction to prove the validity of mathematical equalities and identities.
Proof by mathematical induction
To prove that a statement (A) holds for all natural numbers n:
[1]
Show that (A) holds when n = 1.
[2]
Assume (A) holds when n = k, write down the equation that says so, and use it to show (A) also holds when n = k + 1.
“But that assumes what we are proving!”
No — and this is worth being clear about. You never assume the statement is true everywhere. You assume it is true at one place, and show that would force it at the next place. That is a statement about a link, and it is perfectly honest.
Part [1] knocks the first domino over. Part [2] guarantees every domino topples its neighbour. Do both and the whole row falls — even though you only touched one.
Part [1] — knock the first one over
Show the statement is true when n = 1.
Part [2] — link them together
Show that if it is true at n = k, it must be true at n = k + 1.
Press the button. Then take the links away and press it again.
Without [1]
The links exist but nothing ever starts falling. “Each one would topple the next” is useless if none of them ever falls.
Without [2]
One domino falls and stops. You have proved the statement for n = 1 and nothing else — which is checking, not proving.
Part [2] always works the same way, because the left side at n = k + 1 is just the left side at n = k with one more term added on.
LHS at k + 1 = 1 + 2 + … + k + (k + 1)
The underlined part is exactly what your assumption tells you. Swap it for the assumption's right-hand side, and the rest is algebra.
Do not expand. Factor.
The book's margin says this outright. You are aiming for the right-hand side with k + 1 in place of n — which is a factorised expression. Multiplying everything out walks away from the target; taking out the common ½(k + 1) walks straight towards it.
Use induction to prove that 1 + 2 + 3 + … + n = ½n(n + 1).
- 1
Name the statement so you can refer to it.
let (A) be 1 + 2 + … + n = ½n(n + 1)One line, and it makes everything after it readable.
Work with a partner. One writes part [1], the other part [2]. Then read each other's — part [2] must say where the assumption was used.
Use mathematical induction to prove these equalities.
Every one of these is the same shape. Write part [1]. Write the assumption and label it. Write the left side at k + 1 as (assumption) + (new term). Substitute. Factor. Compare with the target. Close. If your proof is missing any of those seven lines, marks go with it.
Someone claims n² + n + 41 is prime for every natural number n. They check n = 1 through n = 39 and every single one is prime. Have they proved it?
How many natural numbers did they check, and how many are there?
Not writing the assumption down as an equation.
Part [2] must contain a labelled line like "1 + 2 + … + k = ½k(k+1) …… (i)". Without it there is nothing to substitute.
Never saying where the assumption was used.
A proof that does not use (i) anywhere is not an induction proof. Point at the line.
Expanding instead of factorising.
The target is a factorised expression. Take out the common bracket and aim at it.
Writing the new term from memory.
The (k+1)th term comes from substituting k+1 into the pattern. For 2n − 1 that is 2(k+1) − 1, not 2k − 1.
Forgetting the closing sentence.
"From [1] and [2], (A) holds for all natural numbers." The argument is not finished without it.
Sign In to Keep Going
You've reached the end of the free preview. Sign in — and upgrade to Plus or Pro — to keep going with Mathematics.
Full Access
Unlock all 105 lessons