Chapter 2 · Sequences · Concept 5
2-25 Proof of Being a Multiple by Induction
Try it: n³ + 2n at n = 1 gives 3, at n = 2 gives 12, at n = 3 gives 33. All multiples of 3. Try twenty more and they all work too. But 'it worked every time I checked' is exactly the kind of claim that has been wrong before.
Guiding question
How do you prove something is a multiple, for every n at once?
Learning outcome. Apply the principle of mathematical induction to prove the validity of divisibility.
Turn the assumption into an equation
“Is a multiple of a” is not something you can substitute. So the first move of part [2] is always to write it as an equation:
assume it holds at n = k, so
(the expression at k) = a m
for some integer m
Now you have something to substitute, exactly as in lesson 2-23. And at the end:
show the expression at k + 1 takes the form a × (integer)
The last sentence is the proof.
Reaching 9(m + k² + 3k + 3) is not enough on its own. You must say that m + k² + 3k + 3 is an integer — because that is precisely what “multiple of 9” means, and 9 times something unspecified means nothing.
Every claim below can be tested. Four of them hold up. One does not — and that is the point of having the method rather than a table.
Warm Up · is it always a multiple of 9?
| n | value | value over 9 | multiple? |
|---|---|---|---|
| 1 | 36 | 369= 4 | yes ✓ |
| 2 | 99 | 999= 11 | yes ✓ |
| 3 | 216 | 2169= 24 | yes ✓ |
| 4 | 405 | 4059= 45 | yes ✓ |
| 5 | 684 | 6849= 76 | yes ✓ |
| 6 | 1071 | 10719= 119 | yes ✓ |
| 7 | 1584 | 15849= 176 | yes ✓ |
Seven rows all work — which proves nothing at all. A table is a reason to BELIEVE the claim, never a reason to accept it. That is what the induction is for.
Prove that n3 + (n + 1)3 + (n + 2)3 is a multiple of 9 for every natural number n.
- 1
Name the statement.
let (A) be “n3 + (n+1)3 + (n+2)3 is a multiple of 9”Put the whole claim in quotation marks — it is a sentence, not an expression.
Work with a partner. One of you writes the assumption as an equation with an m in it. The other checks the last line actually says the bracket is an integer.
Prove that for any integer n ≥ 1, (n + 1)n − 1 is a multiple of n2.
Careful — this one is different in kind. The thing you are dividing BY changes with n, so stepping from k to k + 1 changes the divisor too. Induction on n is awkward here; the binomial theorem from Chapter 1 does it in three lines.
In the Warm Up, the two k³ terms cancelled exactly. Was that luck, or was it going to happen?
Look at what the assumption contributed and what (k+3)³ contributed.
Not naming the integer m.
Write "= 9m for some integer m". "Is a multiple of 9" cannot be substituted into anything.
Stopping at 9(something).
You must say the bracket is an INTEGER. That sentence is what completes the proof.
Expanding everything instead of grouping.
Pull the assumption's expression out of the expansion first. What is left is usually short.
Skipping n = 1 because the value is 0.
Zero is a multiple of every number. Say "0 = 6 × 0" and move on — do not leave the case out.
Treating a table of values as a proof.
Seven rows working proves nothing. The demo's last claim passes no rows at all, and other false claims survive dozens.
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