Step by step
The question
Question: prove by induction that 1 + 4 + 16 + … + 4ⁿ ⁻ ¹ = (4ⁿ − 1)/3.
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.
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.
3 What we must show
We must show it for k + 1: one more term, 4ᵏ, and every n on the right becomes k + 1.
Careful!
k + 1 goes into every n of the formula.
Adding 1 at the end is not the same.
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.
5 Make both sides the same
Same bottom: 4ᵏ is 3 times it, over 3.
Like terms together.
Now the right side, the one we must get.
A power with k + 1 is one more of the same number.
The same as the left side!
So if it works for k, it works for k + 1.
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.
6 Check
Let's check n = 4 by adding: 1 + 4 + 16 + 64 is 85.
And the formula with 4: also 85.
Right!
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.