13
$\begingroup$

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.

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

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

$\endgroup$
0
7
$\begingroup$

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

$\endgroup$
6
$\begingroup$

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

$\endgroup$
0
6
$\begingroup$

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

$\endgroup$
0
6
$\begingroup$

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

$\endgroup$
4
$\begingroup$

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

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

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.