Worked examples
The question
Question: prove by induction that 1 + 2 + … + n = n(n + 1)/2.
1 + 2 + … + n = n(n + 1)2
Induction works like dominoes.
Push the first one: it is true for n = 1.
Then show each one knocks over the next: if it is true for k, it is true for k + 1.
Then they all fall.
1 Check n = 1
For n = 1 the left side is just the first number, 1.
The right side with n = 1 is also 1.
The first domino falls.
1 = 1(1 + 1)2 = 1
✓ n = 1 works
2 Assume it works for k
Now suppose it works for some whole number k: the sum up to k equals the formula with k.
1 + 2 + … + k = k(k + 1)2
we assume this
3 What we must show
We must show it for k + 1: one more term, (k + 1), and every n on the right becomes k + 1.
1 + 2 + … + k + (k + 1) = (k + 1)((k + 1) + 1)2
Tidy the brackets.
= (k + 1)(k + 2)2
we must get this
Careful!
k + 1 goes into every n of the formula.
Adding 1 at the end is not the same.
Careful: not k(k + 1)2 + 1 ✗
4 Use the assumption
The left side starts with the sum up to k.
By our assumption, that is the formula with k.
We swap it in.
1 + 2 + … + k + (k + 1) = k(k + 1)2 + (k + 1)
5 Make both sides the same
Same bottom: (k + 1) is 2 times it, over 2.
= k(k + 1) + 2(k + 1)2
Open the brackets.
= k2 + k + 2k + 22
Like terms together.
= k2 + 3k + 22
Now the right side, the one we must get.
Open the brackets.
(k + 1)(k + 2)2 = k2 + 2k + k + 22
Like terms together.
= k2 + 3k + 22
The same as the left side!
So if it works for k, it works for k + 1.
= the left side ✓
It is true for n = 1, and each n passes it on to the next.
So it is true for every whole number n.
The proof is done.
true for n = 1, and k → k + 1: true for every n ≥ 1. ∎
6 Check
Let's check n = 4 by adding: 1 + 2 + 3 + 4 is 10.
n = 4: 1 + 2 + 3 + 4 = 10
And the formula with 4: also 10.
Right!
4(4 + 1)2 = 10
Let's look back.
First: check n = 1.
Then: assume it works for k.
Then: what we must show.
Then: use the assumption.
Then: make both sides the same.
Last: check.
▶ Watch it solved
The question
Question: prove by induction that 1 + 2 + 4 + … + 2ⁿ ⁻ ¹ = 2ⁿ − 1.
1 + 2 + 4 + … + 2n − 1 = 2n − 1
Induction works like dominoes.
Push the first one: it is true for n = 1.
Then show each one knocks over the next: if it is true for k, it is true for k + 1.
Then they all fall.
1 Check n = 1
For n = 1 the left side is just the first number, 1.
The right side with n = 1 is also 1.
The first domino falls.
1 = 21 − 1 = 1
✓ n = 1 works
2 Assume it works for k
Now suppose it works for some whole number k: the sum up to k equals the formula with k.
1 + 2 + 4 + … + 2k − 1 = 2k − 1
we assume this
3 What we must show
We must show it for k + 1: one more term, 2ᵏ, and every n on the right becomes k + 1.
1 + 2 + 4 + … + 2k − 1 + 2k = 2k + 1 − 1
we must get this
Careful!
k + 1 goes into every n of the formula.
Adding 1 at the end is not the same.
Careful: not 2k − 1 + 1 ✗
4 Use the assumption
The left side starts with the sum up to k.
By our assumption, that is the formula with k.
We swap it in.
1 + 2 + 4 + … + 2k − 1 + 2k = 2k − 1 + 2k
5 Make both sides the same
Like terms together.
= 2 × 2k − 1
Now the right side, the one we must get.
A power with k + 1 is one more of the same number.
2k + 1 − 1 = 2 × 2k − 1
The same as the left side!
So if it works for k, it works for k + 1.
= the left side ✓
It is true for n = 1, and each n passes it on to the next.
So it is true for every whole number n.
The proof is done.
true for n = 1, and k → k + 1: true for every n ≥ 1. ∎
6 Check
Let's check n = 4 by adding: 1 + 2 + 4 + 8 is 15.
n = 4: 1 + 2 + 4 + 8 = 15
And the formula with 4: also 15.
Right!
24 − 1 = 15
Let's look back.
First: check n = 1.
Then: assume it works for k.
Then: what we must show.
Then: use the assumption.
Then: make both sides the same.
Last: check.
▶ Watch it solved
The question
Question: prove by induction that 1² + 2² + … + n² = n(n + 1)(2n + 1)/6.
12 + 22 + … + n2 = n(n + 1)(2n + 1)6
Induction works like dominoes.
Push the first one: it is true for n = 1.
Then show each one knocks over the next: if it is true for k, it is true for k + 1.
Then they all fall.
1 Check n = 1
For n = 1 the left side is just the first number, 1.
The right side with n = 1 is also 1.
The first domino falls.
1 = 1(1 + 1)(2 × 1 + 1)6 = 1
✓ n = 1 works
2 Assume it works for k
Now suppose it works for some whole number k: the sum up to k equals the formula with k.
12 + 22 + … + k2 = k(k + 1)(2k + 1)6
we assume this
3 What we must show
We must show it for k + 1: one more term, (k + 1)², and every n on the right becomes k + 1.
12 + 22 + … + k2 + (k + 1)2 = (k + 1)((k + 1) + 1)(2(k + 1) + 1)6
Tidy the brackets.
= (k + 1)(k + 2)(2k + 3)6
we must get this
Careful!
k + 1 goes into every n of the formula.
Adding 1 at the end is not the same.
Careful: not k(k + 1)(2k + 1)6 + 1 ✗
4 Use the assumption
The left side starts with the sum up to k.
By our assumption, that is the formula with k.
We swap it in.
12 + 22 + … + k2 + (k + 1)2 = k(k + 1)(2k + 1)6 + (k + 1)2
5 Make both sides the same
Same bottom: (k + 1)² is 6 times it, over 6.
= k(k + 1)(2k + 1) + 6(k + 1)26
Open the brackets.
= 2k3 + k2 + 2k2 + k + 6k2 + 6k + 6k + 66
Like terms together.
= 2k3 + 9k2 + 13k + 66
Now the right side, the one we must get.
Open the brackets.
(k + 1)(k + 2)(2k + 3)6 = 2k3 + 3k2 + 4k2 + 6k + 2k2 + 3k + 4k + 66
Like terms together.
= 2k3 + 9k2 + 13k + 66
The same as the left side!
So if it works for k, it works for k + 1.
= the left side ✓
It is true for n = 1, and each n passes it on to the next.
So it is true for every whole number n.
The proof is done.
true for n = 1, and k → k + 1: true for every n ≥ 1. ∎
6 Check
Let's check n = 4 by adding: 1 + 4 + 9 + 16 is 30.
n = 4: 1 + 4 + 9 + 16 = 30
And the formula with 4: also 30.
Right!
4(4 + 1)(2 × 4 + 1)6 = 30
Let's look back.
First: check n = 1.
Then: assume it works for k.
Then: what we must show.
Then: use the assumption.
Then: make both sides the same.
Last: check.
▶ Watch it solved
