first a few observations $a_n \equiv n \bmod 2$ $a_n|a_{n+2k}$ and $gcd(a_n,a_{n+2k+1})=1$ now return to the main problem: call $n$ a $p-root$ for a prime $p$ if $p|a_n$ and $p$ doesn't divides any $a_i \forall i<n$ claim: if $n$ is $p-root$ then $v_p(a_{n+2k}) \ge (k+1)v_p(a_n)$ proof: $a_n=a_{n-2}.(a_{n-1}+1) \implies v_p(a_{n-1}+1)=v_p(a_n)$ $a_{n+1}=a_{n-1}(a_n+1) \implies a_{n+1} \equiv a_{n-1} \bmod p^{v_p(a_n)}$ $a_{n+1}=a_n(a_{n+1_+1}) \implies p^{2v_p(a_n)}|a_{n+2}$ and its easy to complete these by induction(too lazy to write ) $\blacksquare$ so $v_p(a_{3n}) \ge nv_p(a_n)$ but since $a_5>15 \implies a_n>3n \forall n>5$ and $3n \equiv a_n \bmod 2$ we have $$v_p(a_{a_n})\ge nv_p(a_n)$$and we win

First, note by induction that $a_n \equiv n \pmod{2}$ for all $n$. Now we will show that $\nu_p(a_{a_n}) \geq n \nu_p(a_n)$ for an arbitrary prime $p$. Let $k$ be the first index such that $p$ divides $a_k$. We claim that $a_{k + 2i}$ is divisible by $p$ and $a_{k + 2i - 1} \pmod{p}$ all non-negative integers $i$ .This is a straightforward induction. For convenience's sake, let $a_{k+2i} = b_i$ and $a_{k+2i-1} = c_i$. Claim. The sequence $\nu_p(c_i + 1)$ is non-decreasing. Proof. Let $\nu_p(c_i) = e$. Since $b_i = b_{i-1}(c_i + 1)$, it follows that $p^e$ divides $b_i$. Then \[ c_{i+1} = c_i(b_i + 1) \equiv -1 \cdot 1 \equiv - 1 \pmod{p^e} \]so $\nu_p(c_{i+1} + 1) \geq \nu_p(c_i + 1)$. Let $m = \underset{k + 2i -1 < n}{\max}\nu_p(c_i + 1)$. Then \[ \nu_p(a_n) = \sum_{k + 2i -1 < n} \nu_p(c_i + 1) < m \cdot \frac{n-k+2}{2} . \]On the other hand \[ \nu_p(a_{a_n}) = \sum_{n < k + 2i - 1 < a_n} \nu_p(c_i+1) \geq \nu_p(a_n) + m \cdot \geq \frac{a_n - n}{2}. \]Thus it is sufficient to show that $a_n > n^2 + n$. But this is really not so hard. Compute up to $a_5 = 56 > 5^2 + 5$ and $a_6 = 224 > 6^2 + 6$. For $n \geq 5$ \[ {a_{n+2}} > a_n a_{n+1} > n^2(n+1)^2 > (n+2)^2 + n+2 \]so we are done. @above I think the solution actually does not work because you have only shown $\nu_p(a_{a_n}) \geq n \nu_p(a_n)$ if $n$ is a $p$-root. The argument needs to be slightly refined but this is not so difficult to do.

Here is a size solution. Claim 1. If $p\mid a_n, p\mid a_{n-1}+1$. Proof 1. We proceed by induction. The base case is trivial. If $p\mid a_n=a_{n-2}(a_{n-1}+1)$, either $p\mid a_{n-1}+1$ or $p\mid a_{n-2}$. The first case is trivial. The second case follows from the inductive hypothesis; if $p\mid a_{n-2}$, $p\mid a_{n-3}+1$, so $p\mid a_{n-3}+a_{n-3}a_{n-2}+1=a_{n-1}+1$. We can also easily show $a_n\equiv n(\bmod\; 2)$, so $a_{a_n}=a_{a_n-2} (a_{a_n-1}+1) =\cdots = a_n \prod\limits_{n<i<a_n, 2\nmid i-n} (a_i+1)$. Dividing both sides by $a_n$, we wish to show $(a_n)^{n-1} \mid \prod\limits_{n<i<a_n, 2\nmid i-n} (a_i+1)$. By Claim 1, if $p\mid a_n, p\mid a_i+1$ for all of these $i$. Hence $\nu_p(RHS)=\frac{a_n-n}{2}$ and $\nu_p(a_n^{n-1})=(n-1)\nu_p(a_n)<(n-1)\log_2(a_n)$. Claim 2: $a_n\ge 2^n$ for all $n>7$. We can verify this is true for $n=6,7$. For $n>7, a_n=a_{n-2}(a_{n-1}+1)>2\cdot 2^{n-1}=2^n$. Therefore, since $(n-1)\log_2(x)<<\frac{x-n}{2}$ for $x\ge 2^n$, we're done.