Solution:

The main trick is finding a closed-form expression for $a_{n}$, which requires some experimentation. We will show that $a_{n} = \left(2^{2^{n}+1} + 1\right) / 3$ for all $n$ by induction. It is easy to check that the formula holds for $n=1$. And if it holds for some $n$, then

$$\begin{aligned} a_{n+1} & = \frac{3 a_{n}^{2} + 1}{2} - a_{n} \\ & = \frac{1}{2}\left(3\left[\frac{2^{2^{n}+1} + 1}{3}\right]^{2} + 1\right) - \frac{2^{2^{n}+1} + 1}{3} \\ & = \frac{1}{2}\left(\frac{\left(2^{2^{n}+1}\right)^{2} + 2\left(2^{2^{n}+1}\right) + 1}{3} + 1\right) - \frac{2^{2^{n}+1} + 1}{3} \\ & = \frac{1}{2}\left(\frac{2^{2^{n+1}+2} + 2\left(2^{2^{n}+1}\right) + 4}{3}\right) - \frac{2^{2^{n}+1} + 1}{3} \\ & = \frac{2^{2^{n+1}+1} + 2^{2^{n}+1} + 2}{3} - \frac{2^{2^{n}+1} + 1}{3} \\ & = \frac{2^{2^{n+1}+1} + 1}{3}, \end{aligned}$$

giving the induction step.

Now, by Euler's theorem, $3^{k}$ divides $2^{2 \cdot 3^{k-1}} - 1$, for any nonnegative integer $k$, since $\phi\left(3^{k}\right)$ (i.e. the number of integers in $\{1,2, \ldots, 3^{k}\}$ relatively prime to $3^{k}$) equals $2 \cdot 3^{k-1}$. But notice that $2^{2 \cdot 3^{k-1}} - 1 = \left(2^{3^{k-1}} - 1\right)\left(2^{3^{k-1}} + 1\right)$, and $3^{k-1}$ is odd $\Rightarrow 2^{3^{k-1}} \equiv 2 \pmod{3} \Rightarrow 2^{3^{k-1}} - 1$ is relatively prime to $3^{k}$, so, in fact, $3^{k}$ divides $2^{3^{k-1}} + 1$. Also, for any integers $c, d$ with $d$ odd, $2^{c} + 1 \mid 2^{c d} + 1$. We conclude that $3^{k} \mid 2^{a} + 1$ whenever $3^{k-1} \mid a$ and $a$ is odd.

Applying this result twice in succession, we find that $3^{k} \mid 2^{3^{k}} + 1$ and then that $3^{k+1} \mid 2^{2^{3^{k}} + 1} + 1$, so that $3^{k} \mid \left(2^{2^{3^{k}} + 1} + 1\right) / 3 = a_{3^{k}}$ for any integer $k \geq 0$, and this is what we wanted to prove.