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?

Where you fail, is in assuming exponents mod the modulus works. It wouldn't generally. the exponent is mod 6, when doing mod 9. So you get it equivalent to: $$128\cdot 2^{3k}=128\cdot8^k$$ Which then depends on parity of k (because 8's order mod 9 is 2).
