prove that $2^n+2^{n-1}+2^{n-2}+8^n-8^{n-2}$ is a multiple of 7

Question

Prove that a number $2^n+2^{n-1}+2^{n-2}+8^n-8^{n-2}$ is a multiple of 7 for every natural $n\ge2$. I am not sure how to start.

Answer 1

You can factor it as

$$2^{n-2}(2^2+2+1)+8^{n-2}(64-1).$$

Answer 2

This is relatively easy to solve even without noticing some clever factorization, simply by checking several possible cases.

It suffices to check what are remainder of powers of $2$ modulo $7$.

You can see that:
$2^0 \equiv 1 \pmod 7$
$2^1 \equiv 2 \pmod 7$
$2^2 \equiv 4 \pmod 7$
$2^3 \equiv 1 \pmod 7$
$2^4 \equiv 2 \pmod 7$
$2^5 \equiv 4 \pmod 7$
We see, that this repeats with period $3$. We get that $2^k\equiv 1\pmod 7$ if $k$ is multiple of $3$, $2^k\equiv 2\pmod7$ if the remainder modulo $3$ is $1$ and $2^k\equiv 4\pmod 7$ in the remaining case.

Let us look at the case $n=3k+1$.
Then we get
$2^n = 2^{3k+1} \equiv 2 \pmod 7$
$2^{n-1} = 2^{3k} \equiv 1 \pmod 7$
$2^{n-2} = 2^{3(k-1)+1} \equiv 4 \pmod 7$
$8^n=2^{3n} \equiv 1 \pmod 7$
$8^{n-2} = 2^{3(n-2)} \equiv 1 \pmod 7$
(In fact, for the powers of $8$ it is easier to notice that $8^n \equiv 1^n \equiv 1 \pmod 7$.)

By summing the above congruences we get
$2^n+2^{n-1}+2^{n-2}+8^n - 8^{n-2} \equiv 2+1+4+1-1 \equiv 7 \equiv 0 \pmod 7$.

I leave remaining cases $n=3k$ and $n=3k+2$ for you. (And, as you have seen in another answer, if you think about this a bit, you should be able to come up with a solution where you don't need to try various cases.)

Answer 3

The base case is true, $T_0=4+2+1+64-8=63$ is a multiple of $7$.

Now let us relate $T_{n+1}$ to $T_n$:

$$T_{n+1}=2.2^n+2.2^{n-1}+2.2^{n-2}+8.8^n-8.8^{n-2}.$$

Subtracting $T_n$, we have

$$T_{n+1}-T_n=2^n+2^{n-1}+2^{n-2}+7.8^n-7.8^{n-2}.$$

We can discard the last two terms, obviously multiples of $7$. Remains to prove that $2^n+2^{n-1}+2^{n-2}$ is a multiple of $7$.

The base case is true, $U_0=4+2+1=7$.

Now let us relate $U_{n+1}$ to $U_n$:

$$U_{n+1}=2.2^n+2.2^{n-1}+2.2^{n-2}=2.U_n.$$ As $U_n$ is a multiple of $7$, so is $U_{n+1}$.