# Induction proof, divisibility

I'm struggling with an induction problem here.

I have to prove that $2^{2^n}- 6$ (two to the power of two to the power of $n$ minus six) is divisible by $10$.

I already figured some steps and I also figured it's only divisible for n being an even number. No idea how to prove it though.

I got this so far:

step I:

$2^{2^2} - 6 = 10 / 10 = 1$ TRUE

step II: Assume for $n = k$

$2^{2^k} - 6 = 10M$

Step III: $n = k+1$

$2^{2^{k+1}} - 6$

$2^{2^k 2^2} -6$

by assumption: $2^{2^k} = 10M + 6$

$(10M + 6) x 4 - 6 = 40M-18$ <-- which is not divisible by 10 as you can't factor it out. But i figured this induction problem is divisible for even integers of $K$.

• You have error in induction step. $2^{2^{k+1}}=2^{2^k\cdot 2} = (2^{2^k})^2$. So you have $(10M+6)^2-6 = 100M^2 + 120M + 30$. Jun 4 '15 at 11:38

$$2^{2^k}=10M+6$$
$$(2^{2^k})^2=2^{2^{k+1}}=100M^2+36+120M=10(10M^2+12M+3)+6$$ And finally:
$$2^{2^{k+1}}-6=10(10M^2+12m+3)$$

• Are you sure this is correct? From my understanding you've just proven that 2^2^(K+1) - 6 is divisible by 10. Le'ts say: 2^2^(2+1) - 6 = 2^6 -6 = 58 Jun 4 '15 at 11:56
• This is just the inductive step, not the whole proof. Jun 4 '15 at 11:59
• what is your question exactly? You want to prove that $2^{2^n}$ is divisible by 10 when $n\ge 2$? isn't it? So by induction on $n$, i proved it. Jun 4 '15 at 12:03
• @imdumb $2^{2^k}$ means $2^{(2^k)}$, not $(2^2)^k$, so $2^{2^3}-6=250$, which is divisible by $10$. Jun 4 '15 at 12:04
• ah that's what i've done wrong. My apologies - thank you! Jun 4 '15 at 12:05

Hint $\,\ f_n\! = 2^{2^n}\Rightarrow\,f_{n+1}= f_n^2,\$ so $\,{\rm mod}\ 10\!:\ \color{#c00}{f_n\equiv 6}\,\Rightarrow\, f_{n+1}\equiv \color{#c00}{f_n}^2 \equiv \color{#c00}6^2\equiv 6$

• The induction base is $\ f_2 = 16\equiv 6\pmod{10}\ \$ Jun 4 '15 at 14:53