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

• Hint: $2^{2^{k}}$ is a common factor to all terms of $b-a$ – André Armatowski Feb 7 at 20:16
• For set inclusion use \in, not \epsilon. – K.defaoite Feb 7 at 20:16
• Just saying, it also works for $n=0$. – steven gregory Feb 8 at 1:45

## 7 Answers

$$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)}$$

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

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

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

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

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

• $8\cdot 2^{2^{k}} \neq 4^{2\cdot2^{k}}.$ Did you have something else in mind? – David K Feb 7 at 20:33

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.

• This is my first answer on this platform using formatting. Kindly provide me with tips if there are mistakes. – K.Raghuram Chakravorthy Feb 14 at 13:33