Prove 2 + 6 + 18 + ... + 2 × 3^(n - 1) = 3^n

Step by step

The question

Question: prove by induction that 2 + 6 + 18 + … + 2 × 3ⁿ ⁻ ¹ = 3ⁿ − 1.

2 + 6 + 18 + … + 2 × 3^{n − 1} = 3ⁿ − 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, 2.

The right side with n = 1 is also 2.

The first domino falls.

2 = 3¹ − 1 = 2

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

2 + 6 + 18 + … + 2 × 3^{k − 1} = 3^k − 1

we assume this

3 What we must show

We must show it for k + 1: one more term, 2 × 3ᵏ, and every n on the right becomes k + 1.

2 + 6 + 18 + … + 2 × 3^{k − 1} + 2 × 3^k = 3^{k + 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 3^k − 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.

2 + 6 + 18 + … + 2 × 3^{k − 1} + 2 × 3^k = 3^k − 1 + 2 × 3^k

5 Make both sides the same

Like terms together.

= 3 × 3^k − 1

Now the right side, the one we must get.

A power with k + 1 is one more of the same number.

3^{k + 1} − 1 = 3 × 3^k − 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: 2 + 6 + 18 + 54 is 80.

n = 4: 2 + 6 + 18 + 54 = 80

And the formula with 4: also 80.

Right!

3⁴ − 1 = 80

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.

Answer