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.
 A: 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.$
A: $ 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$.
A: 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$.
A: 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.$)
A: $7|8\cdot 2^{2^{k}}+2\cdot 2^{2^{k}}-2\cdot 2^{2^{k}}-2^{2^{k}}$
$7| 2^{2^{k}}\cdot (8+2-2-1)$
$7| 2^{2^{k}}\cdot (7)$
I think I proved it.
A: Prove by Induction that
$ 7| {4^{2^n} + 2^{2^n} + 1} , ∀ n ∈ N  $
Base case:
$7 | 4^{2^1} + 2^{2^1} + 1, $
7|7⋅3
Which is true.
Now, having n=k, we assume that:
$7|4^{2^k} + 2^{2^k} + 1, ∀  k ∈ ℕ $
We have to prove that for n=k+1 that,
$7| 4^{2^{k+1}} + 2^{2^{k+1}} + 1, ∀ k ∈ ℕ $
$ 4^{2^{k+1}} + 2^{2^{k+1}} + 1 = 4^{2*2^k} + 2^{2*2^k} + 1 $
$ = {4^{2^k}}^2 + {2^{2^k}}^2 + 1 $
Put $ {4^{2^k}} = a, {2^{2^k}} = b $
$ ∴ {(4^{2^k})}^2 + {(2^{2^k})}^2 + 1 = a^2 + b^2 + 1   $
Also,
$  (a+b+1)(a+b-1) = a^2 + b^2 + 2ab - 1 $
Since $ 7|a+b+1 $,
$ 7| a^2 + b^2 + 2ab - 1    ...(1) $
$ ab-1 = {8^{2^k}} - 1 $
For  n ∈ ℕ, $ 8^n = (7+1)^n $
= (Multiple of 7) + 1
(Theorem of Binomial Expansion)
$ ∴ 8^n -1 = 7p $
Where p ∈ ℕ if n ∈ ℕ
$ ∴ 7| ab - 1       ....(2) $
Subtracting Equation (2) from equation (1),
$ 7| a^2 + b^2 + 2ab - 1 -2*(ab-1) $
$ ∴ 7| a^2 + b^2 + 1 $
ie
$$7| 4^{2^{k+1}} + 2^{2^{k+1}} + 1, ∀ k ∈ ℕ $$
if
$7| 4^{2^{k}} + 2^{2^{k}} + 1, ∀ k ∈ ℕ $
Hence, by principle of Mathematical Induction, the above statement is proved to be true.
A: $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)}$
