Prove 4^n - 1 is divisible by 3 by induction Step by Step

Step by step

The question

Question: prove by induction that 4ⁿ − 1 is divisible by 3, for every whole number n.

4ⁿ − 1 is divisible by 3

Like dominoes: show it for n = 1, then show that k passes it on to k + 1.

1 Check n = 1

For n = 1: 3, and that is 3 × 1.

Divisible by 3: the first domino falls.

4¹ − 1 = 3 = 3 × 1

2 Assume it works for k

Suppose it works for k: 4ᵏ − 1 is a multiple of 3.

So it is 3 times some whole number.

Call it m.

4^k − 1 = 3m

m is a whole number

Move the rest to the other side: 4ᵏ equals 3m + 1.

We will need this.

4^k = 3m + 1

3 What we must show

We must show the same for k + 1: every n becomes k + 1.

= 4^{k + 1} − 1 is divisible by 3

Careful!

One more power means one more times the number.

It is 4 times as big, not 1 more.

Careful: not 4^{k + 1} = 4^k + 1 ✗

4 Use the assumption

One more power: 4 times the power with k.

4^{k + 1} − 1 = 4 × 4^k − 1

4^{k + 1} = 4 × 4^k

Now swap in 3m + 1 for 4ᵏ.

= 4(3m + 1) − 1

Open the bracket.

= 12m + 4 − 1

Like terms together.

= 12m + 3

5 Take out 3

Every term has a 3 in it.

Take out 3: 3(4m + 1).

= 3(4m + 1)

4m + 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 3 for n = 1, and k → k + 1: for every n. ∎

6 Check

Let's check n = 3: it gives 63.

n = 3: 4³ − 1 = 63

63 is 3 times 21.

Divisible by 3.

Right!

63 = 3 × 21

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 3.

Last: check.

Answer