Prove that $2^{2^{2^{\cdot^{\cdot^{2}}}}} \mod 9 = 7$ 
Prove that $\underbrace{2^{2^{2^{\cdot^{\cdot^{2}}}}}}_{2016  \mbox{ 
times}} \mod 9 = 7$

I think that it can be done by induction: 
Base:
$2^{2^{2^{2}}} \equiv 2^{16} \equiv 2^8 \cdot 2^8 \equiv 2^4 \cdot 2^4 \cdot2^4 \cdot2^4 \equiv 7^2 \cdot 7^2 \equiv 4 \cdot 4 \equiv 16 \equiv 7$

Assume that it is true for $n$ times. 
Let  $a_n = \underbrace{2^{2^{2^{\cdot^{\cdot^{2}}}}}}_{n  \mbox{ 
times}}$
$$ a_{n+1} = 2^{a_n} = 2^{9k+7} = 2^7 \cdot 2^{9k} \equiv 128 \cdot 1 \equiv 2 \neq 7 $$
Where did I go wrong?

For the correct way to do modular exponent reduction see here. Using that method
$\!\!\bmod 9\!:\,\ 2^{\Large\color{#c00} 6}\equiv 1\ \ {\rm thus}\ \ 2^{\large N}\equiv\, 2^{\large N\Large \bmod\, \color{#c00}6}\ $ 
$\text{Applying that here}\!:\   2^{\Large {2^{\Large 2K}}}\!\!\equiv\, 2^{\Large \color{#0a0}{2^{\Large 2K}}\!\bmod\color{#c00} 6}\!\equiv  2^{\Large\color{#0a0} 4}\equiv 7$
$\text{since we have that:}$ $\bmod \color{#c00}6\!:\,\ \color{#0a0}{2^{\large 2K}}\!\equiv 4^{\large K}\!\equiv\color{#0a0} 4,\,$ by $\,4^{\large 2}\equiv 4\,$ and induction (or by here).
