Worked examples
The question
Question: prove by induction that 6ⁿ − 1 is divisible by 5, for every whole number n.
6n − 1 is divisible by 5
Like dominoes: show it for n = 1, then show that k passes it on to k + 1.
1 Check n = 1
For n = 1: 5, and that is 5 × 1.
Divisible by 5: the first domino falls.
61 − 1 = 5 = 5 × 1
2 Assume it works for k
Suppose it works for k: 6ᵏ − 1 is a multiple of 5.
So it is 5 times some whole number.
Call it m.
6k − 1 = 5m
m is a whole number
Move the rest to the other side: 6ᵏ equals 5m + 1.
We will need this.
6k = 5m + 1
3 What we must show
We must show the same for k + 1: every n becomes k + 1.
= 6k + 1 − 1 is divisible by 5
Careful!
One more power means one more times the number.
It is 6 times as big, not 1 more.
Careful: not 6k + 1 = 6k + 1 ✗
4 Use the assumption
One more power: 6 times the power with k.
6k + 1 − 1 = 6 × 6k − 1
6k + 1 = 6 × 6k
Now swap in 5m + 1 for 6ᵏ.
= 6(5m + 1) − 1
Open the bracket.
= 30m + 6 − 1
Like terms together.
= 30m + 5
5 Take out 5
Every term has a 5 in it.
Take out 5: 5(6m + 1).
= 5(6m + 1)
6m + 1 is a whole number
So it works for k + 1 too.
True for n = 1, and passed on each time: true for every whole number n.
The proof is done.
divisible by 5 for n = 1, and k → k + 1: for every n. ∎
6 Check
Let's check n = 3: it gives 215.
n = 3: 63 − 1 = 215
215 is 5 times 43.
Divisible by 5.
Right!
215 = 5 × 43
Let's look back.
First: check n = 1.
Then: assume it works for k.
Then: what we must show.
Then: use the assumption.
Then: take out 5.
Last: check.
Answer 6m + 1 is a whole number
▶ Watch it solved
The question
Question: prove by induction that 7ⁿ − 2ⁿ is divisible by 5, for every whole number n.
7n − 2n is divisible by 5
Like dominoes: show it for n = 1, then show that k passes it on to k + 1.
1 Check n = 1
For n = 1: 5, and that is 5 × 1.
Divisible by 5: the first domino falls.
71 − 21 = 5 = 5 × 1
2 Assume it works for k
Suppose it works for k: 7ᵏ − 2ᵏ is a multiple of 5.
So it is 5 times some whole number.
Call it m.
7k − 2k = 5m
m is a whole number
Move the rest to the other side: 7ᵏ equals 2ᵏ + 5m.
We will need this.
7k = 2k + 5m
3 What we must show
We must show the same for k + 1: every n becomes k + 1.
= 7k + 1 − 2k + 1 is divisible by 5
Careful!
One more power means one more times the number.
It is 7 times as big, not 1 more.
Careful: not 7k + 1 = 7k + 1 ✗
4 Use the assumption
One more power: 7 times the power with k.
7k + 1 − 2k + 1 = 7 × 7k − 2 × 2k
7k + 1 = 7 × 7k
Now swap in 2ᵏ + 5m for 7ᵏ.
= 7(2k + 5m) − 2 × 2k
Open the bracket.
= 35m + 7 × 2k − 2 × 2k
Like terms together.
= 5 × 2k + 35m
5 Take out 5
Every term has a 5 in it.
Take out 5: 5(2ᵏ + 7m).
= 5(2k + 7m)
2ᵏ + 7m is a whole number
So it works for k + 1 too.
True for n = 1, and passed on each time: true for every whole number n.
The proof is done.
divisible by 5 for n = 1, and k → k + 1: for every n. ∎
6 Check
Let's check n = 3: it gives 335.
n = 3: 73 − 23 = 335
335 is 5 times 67.
Divisible by 5.
Right!
335 = 5 × 67
Let's look back.
First: check n = 1.
Then: assume it works for k.
Then: what we must show.
Then: use the assumption.
Then: take out 5.
Last: check.
Answer 2ᵏ + 7m is a whole number
▶ Watch it solved
The question
Question: prove by induction that 2n³ + 3n² + n is divisible by 6, for every whole number n.
2n3 + 3n2 + n is divisible by 6
Like dominoes: show it for n = 1, then show that k passes it on to k + 1.
1 Check n = 1
For n = 1: 6, and that is 6 × 1.
Divisible by 6: the first domino falls.
2 × 13 + 3 × 12 + 1 = 6 = 6 × 1
2 Assume it works for k
Suppose it works for k: 2k³ + 3k² + k is a multiple of 6.
So it is 6 times some whole number.
Call it m.
2k3 + 3k2 + k = 6m
m is a whole number
3 What we must show
We must show the same for k + 1: every n becomes k + 1.
= 2(k + 1)3 + 3(k + 1)2 + (k + 1) is divisible by 6
Careful!
A bracket to a power is the bracket times itself.
Every part times every part.
Careful: not (k + 1)³ = k³ + 1 ✗
4 Use the assumption
Each power of the bracket is the bracket times itself.
2(k + 1)3 + 3(k + 1)2 + (k + 1) = 2(k + 1)(k + 1)(k + 1) + 3(k + 1)(k + 1) + (k + 1)
Open the brackets.
= 2k3 + 2k2 + 2k2 + 2k + 2k2 + 2k + 2k + 2 + 3k2 + 3k + 3k + 3 + k + 1
Like terms together.
= 2k3 + 9k2 + 13k + 6
Look for the old one inside: 2k³ + 3k² + k.
The rest is left over.
= (2k3 + 3k2 + k) + 6k2 + 12k + 6
By our assumption, the old one is 6m.
= 6m + 6k2 + 12k + 6
5 Take out 6
Every term has a 6 in it.
Take out 6: 6(k² + 2k + m + 1).
= 6(k2 + 2k + m + 1)
k² + 2k + m + 1 is a whole number
So it works for k + 1 too.
True for n = 1, and passed on each time: true for every whole number n.
The proof is done.
divisible by 6 for n = 1, and k → k + 1: for every n. ∎
6 Check
Let's check n = 3: it gives 84.
n = 3: 2 × 33 + 3 × 32 + 3 = 84
84 is 6 times 14.
Divisible by 6.
Right!
84 = 6 × 14
Let's look back.
First: check n = 1.
Then: assume it works for k.
Then: what we must show.
Then: use the assumption.
Then: take out 6.
Last: check.
Answer k² + 2k + m + 1 is a whole number
▶ Watch it solved
