Dear Uncle Colin,

How would you prove that $7^{n+1} + 8 ^{2n-1}$ is a multiple of 57 for integer $n ≥ 1$?

I’m Not Doing Unnecessary Calculations To Investigate Our Numbers

Hi, INDUCTION, and thanks for your message!

Well not with that attitude, you aren’t.

For convenience’s sake, I’m going to write the value of the expression when $n=k$ as $V(k)$. Let’s have a look at the three steps:

The base case

Elsewhere in your message, you showed that you’d worked out the base case, but I’ll go through it for the benefit of everyone else.

We need to work out $V(1)$ and show that it’s a multiple of 57. That’s not too hard: if $n=1$, then we get $7^2 + 8^1$, which is 57, and that’s trivially a multiple of 57.

The induction step

For this part, we want to show that if $V(k)$ is a multiple of 57, then so is $V(k+1)$. ((We often say “assume”, but I find that leads to more confusion.))

What do we mean by this? We need to show that if $7^{k+1} + 8^{2k-1}$ is a multiple of 57, then so is $7^{k+2} + 8^{2k+1}$.

So, suppose $V(k)$ – that is, $7^{k+1} + 8^{2k-1} = 57n$ for some integer $n$.

How does $V(k+1)$ relate to $V(k)$? Let’s start with $7^{k+2} + 8^{2k+1}$, and write it as $7\left(7^{k+1}\right) + 64\left(8^{2k-1}\right)$. At this point, take a deep breath: the next step isn’t obvious.

Well, we could take out seven copies of $V(k)$ there. Where does that lead us?

We get $7V(k) + 57\left(8^{2k-1}\right)$ – aha! So it’s $7\times 57n + 57\left(8^{2k-1}\right)$, or $57\left(7n + 8^{2k-1}\right)$, which is clearly a multiple of 57.

That’s shown it: if $V(k)$ is a multiple of 57, then so is $V(k+1)$.

The conclusion

Last up, we need to write down what we’ve done:

  • $V(1) = 57$, so the proposition holds for the base case.
  • If $V(k)=57n$, then $V(k+1) = 57\left(7n + 8^{2k-1}\right)$, so if $V(k)$ is a multiple of 57 then so is $V(k+1)$.
  • Therefore, the proposition holds for $V(2)$, $V(3)$ and all $V(n)$ where integer $n ≥ 1$.