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.

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.
