Divisibility by 7 Proof by Induction

Prove by Induction that

$$7|4^{2^{n}}+2^{2^{n}}+1,\; \forall n\in \mathbb{N}$$

Base case:

$$ \begin{aligned} 7&|4^{2^{1}}+2^{2^{1}}+1,\\ 7&|7\cdot 3 \end{aligned}$$ Which is true.

Now, having $n=k$, we assume that:

$$7|4^{2^{k}}+2^{2^{k}}+1,\;\; \forall k\in \mathbb{N}$$

We have to prove that for $n=k+1$ that,

$$7|4^{2^{k+1}}+2^{2^{k+1}}+1,\;\; \forall k\in \mathbb{N}$$

We know that if $a$ is divisible by 7 then $b$ is divisible by 7 iff $b-a$ is divisible by 7.

Then, $$ \begin{aligned} b-a &= 4^{2^{k+1}}+2^{2^{k+1}}+1 - (4^{2^{k}}+2^{2^{k}}+1)\\ &= 4^{2^{k+1}}+2^{2^{k+1}} - 4^{2^{k}}-2^{2^{k}}\\ &= 4^{2\cdot 2^{k}}+2^{2\cdot 2^{k}} - 4^{2^{k}}-2^{2^{k}} \end{aligned} $$

I get stuck here, please help me.

Solution 1:

$b-a=4^{2\cdot2^k}-4^{2^k}+2^{2\cdot2^k}-2^{2^k}$

$=4^{2^k}(4^{2^k}-1)+2^{2^k}(2^{2^k}-1)$

$=4^{2^k}(2^{2^k}-1)(2^{2^k}+1)+2^{2^k}(2^{2^k}-1)$

$=(2^{2^k}-1)(8^{2^k}+4^{2^k}+2^{2^k})$

$=(2^{2^k}-1)2^{2^k}\color{blue}{(4^{2^k}+2^{2^k}+1)}$

Solution 2:

Divisibility by $7$ is congruence to zero modulo $7.$ So we might get some insights by looking at the numbers' congruences mod $7$.

Note that $x^{2^{k+1}} = x^{2^k\cdot 2} = \left(x^{2^k}\right)^2.$ That is, every time we add $1$ to the exponent $k$ in $2^{2^k}$ or $4^{2^k}$, we square the number.

So let's try applying these two ideas: do the arithmetic modulo $7$; and try the first few values of $n$ and see what happens.

So what happens is \begin{align} 2^2 \equiv 4 \pmod7,\\ 4^2 \equiv 2 \pmod7.\\ \end{align}

That is, \begin{align} \text{for } n &= 1, & 4^{2^1} + 2^{2^1} + 1 = 4^2 + 2^2 + 1 &\equiv 2 + 4 + 1 \pmod7,\\ \text{for } n &= 2, & 4^{2^2} + 2^{2^2} + 1 \equiv 2^2 + 4^2 + 1 &\equiv 4 + 2 + 1 \pmod7,\\ \text{for } n &= 3, & 4^{2^3} + 2^{2^3} + 1 \equiv 4^2 + 2^2 + 1 &\equiv 2 + 4 + 1 \pmod7,\\ \end{align} and so forth.

You should now know the congruence classes of $4^{2^n}$ and $2^{2^n}$ for every $n$ and be able to prove the obvious pattern of congruences for alternating odd and even $n$ by induction. This is just a little less elegant that some of the other proofs in that you may find it necessary to have two cases in the inductive step, one for odd $k$ and one for even $k.$

Solution 3:

$ b - a = 4^{2^{k+1}} + 2^{2^{k+1}} - 4^{2^k}-2^{2^k}$

An intermediate step: notice $4=2^2$, so we have that $b-a = 2^{2^{k+2}} + 2^{2^{k+1}} - 2^{2^{k+1}}-2^{2^k} = 2^{2^{k+2}} -2^{2^k} $

Notice that each term is divisible by $2^{2^k}$, and $7$ does not divide $2^{2^k}$.

Now $\frac{b-a}{2^{2^k}} = 2^{2^{k+2} - 2^k} -2^{2^k - 2^k} = 2^{3 \times 2^k} - 2^0 = 8^{2^k} -1$

Now it is more of a bonus fact that $8^m -1$ is always divisible by $7$.

Solution 4:

Modulo $7,$ $4^{2^n}+2^{2^n}+1 \equiv 2+4+1\equiv 0$ when $n$ is odd, and to $4+2+1\equiv 0$ when $n$ is even.

(Start with $4^{2^n}\equiv 2$ and $2^{2^n}\equiv 4$ when $n=1.$)

Solution 5:

Other answers have shown how you could continue with what you had. But just for interest, here's another proof, which doesn't use the difference, but the quotient:

Let's call the formula

$$ a_n = 4^{2^n} + 2^{2^n} + 1 $$

You already showed that $a_1 = 21$ is a multiple of $7$. (So is $a_0 = 4^1+2^1+1 = 7$, so we can actually prove it for every non-negative integer $n$.)

With so many $2$'s involved, a substitution $4=2^2$ seems worth trying:

$$ a_n = (2^2)^{2^n} + 2^{2^n} + 1 = 2^{2 \cdot 2^n} + 2^{2^n} + 1 $$

The multiple exponent operations are a bit confusing, but we can abstract them out by noticing $2^{2 \cdot 2^n} = (2^{2^n})^2$, so if we define $x_n = 2^{2^n}$, then

$$ a_n = x_n^2 + x_n + 1 $$

Take $7 | a_n$ as the inductive hypothesis, and look at the next iteration:

$$ x_{n+1} = 2^{2^{n+1}} = 2^{2 \cdot 2^n} = (2^{2^n})^2 = x_n^2 $$

$$ a_{n+1} = x_{n+1}^2 + x_{n+1} + 1 = x_n^4 + x_n^2 + 1 $$

But this factors as

$$ a_{n+1} = (x_n^2 - x_n + 1) (x_n^2 + x_n + 1) = (x_n^2 - x_n + 1) a_n $$

Since $x_n$ is a positive integer, $(x_n^2 - x_n + 1)$ is also a positive integer. Since $7 | a_n$, we also have $7 | a_{n+1}$. Therefore by induction, $7 | a_n$ for every natural $n$.