CroatianCompetitions

We will prove by induction that for all $n \ge 0$, $a_n \equiv -1 \pmod{10^{2^n}}$.

Base case: $n = 0$. $a_0 = 9 \equiv -1 \pmod{10}$, since $9 + 1 = 10$.

Inductive step: Assume $a_n \equiv -1 \pmod{10^{2^n}}$.

Consider $a_{n+1} = 3a_n^4 + 4a_n^3$.

Let $m = 10^{2^n}$. Then $a_n \equiv -1 \pmod{m}$, so $a_n = m t - 1$ for some integer $t$.

Compute $a_{n+1}$ modulo $m^2 = 10^{2^{n+1}}$:

$a_{n+1} = 3a_n^4 + 4a_n^3$

Expand $a_n^3$ and $a_n^4$:

$a_n^3 = (m t - 1)^3 = m^3 t^3 - 3 m^2 t^2 + 3 m t - 1$
$a_n^4 = (m t - 1)^4 = m^4 t^4 - 4 m^3 t^3 + 6 m^2 t^2 - 4 m t + 1$

So:
$3a_n^4 = 3(m^4 t^4 - 4 m^3 t^3 + 6 m^2 t^2 - 4 m t + 1) = 3 m^4 t^4 - 12 m^3 t^3 + 18 m^2 t^2 - 12 m t + 3$
$4a_n^3 = 4(m^3 t^3 - 3 m^2 t^2 + 3 m t - 1) = 4 m^3 t^3 - 12 m^2 t^2 + 12 m t - 4$

Add:
$3a_n^4 + 4a_n^3 =$
$[3 m^4 t^4]$
$+ [-12 m^3 t^3 + 4 m^3 t^3] = -8 m^3 t^3$
$+ [18 m^2 t^2 - 12 m^2 t^2] = 6 m^2 t^2$
$+ [-12 m t + 12 m t] = 0$
$+ [3 - 4] = -1$

So:
$a_{n+1} = 3 m^4 t^4 - 8 m^3 t^3 + 6 m^2 t^2 - 1$

Now, $m^2 = 10^{2^{n+1}}$, so all terms with $m^2$ or higher are divisible by $m^2$ and thus $\equiv 0 \pmod{m^2}$.

Therefore, $a_{n+1} \equiv -1 \pmod{m^2}$, i.e., $a_{n+1} \equiv -1 \pmod{10^{2^{n+1}}}$.

By induction, $a_n \equiv -1 \pmod{10^{2^n}}$ for all $n$.

For $n = 11$, $a_{11} \equiv -1 \pmod{10^{2^{11}}}$, so the decimal representation of $a_{11}$ ends with $2^{11} = 2048$ digits 9.

In particular, it ends with at least 2011 digits 9.