Prove 3^(2n) - 1 is divisible by 8 by induction

Step by step

The question

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

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

1 Check n = 1

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

Divisible by 8: the first domino falls.

2 Assume it works for k

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

So it is 8 times some whole number.

Call it m.

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

We will need this.

3 What we must show

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

Careful!

One more power means one more times the number.

It is 9 times as big, not 1 more.

4 Use the assumption

One more power: 3² times the power with k.

Now swap in 8m + 1 for 3²ᵏ.

Open the bracket.

Like terms together.

5 Take out 8

Every term has an 8 in it.

Take out 8: 8(9m + 1).

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.

6 Check

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

728 is 8 times 91.

Divisible by 8.

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: take out 8.

Last: check.