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.

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