Taking a closer look at my proof in http://www.mathlinks.ro/viewtopic.php?p=849418.

Induction

lazizbek42 wrote: Induction Yes, I solved it that way but the induction isn't easy.

For completeness' sake, I will simply copy my recent reply on https://artofproblemsolving.com/community/c146h150506p849417. We will show that with $a_1 = 2, a_2 = 2^2, a_3 = 2^{2^{2}}, \ldots$, we have that $a_i \equiv a_j \pmod{n}$ for all $i,j > \log_2(n)$. First note that if $a_k$ is congruent to $a_{k+1} = 2^{a_k}$ modulo $n$ for some $k$, then $a_k \equiv {a_j} \pmod{n}$, for all $j > k$ by induction. This means that we are done as soon as we can find two consecutive terms which are congruent modulo $n$. Now assume by induction that $a_k \equiv a_{k+1} \pmod{n}$ for all $n < 2^k$, which is trivially true for $k = 1$. We will prove that $a_{k+1} \equiv a_{k+2} \pmod{n}$ holds for all $n < 2^{k+1}$. So assume $2^k \le n < 2^{k+1}$ and write $n = l2^m$ with $l$ odd. First we will deal with the even case; assume that $m \ge 1$. We actually intend to show that already $a_k \equiv a_{k+1} \pmod{n}$ in this case. First it is clear that $a_i \equiv a_j \equiv 0 \pmod{2^m}$ for all $i,j \ge k \ge m$, so it is sufficient to show $a_k \equiv a_{k+1} \pmod{l}$. But since $l < 2^k$, this already follows from the induction hypothesis. So now let's move on to the odd case and assume $m = 0$. Since $\varphi(n)$ is even, we obtain (either by what we just proved or the induction hypothesis) that $a_{k+1} \equiv a_k \pmod{\varphi(n)}$. But by Euler's Theorem this implies $a_{k+1} = 2^{a_{k}} \equiv 2^{a_{k+1}} = a_{k+2} \pmod{n}$.