Isn't this just a trivial strong induction? Verify base cases. Let $n=2k$. Then, $a_n=a_{2k} = 2k\cdot a_k$. By inductive hypothesis, it is known that $a_k>k^2$. Thus, $a_n=a_{2k}>2k^3$. It boils down checking $2k^3>(2k)^2$, that is, $k>2$, which is immediate. Similarly, if $n=2k+1$, then $a_n=(2k+1)a_k$, and $a_k>k^2$ by inductive hypothesis. Thus, it boils down verifying $(2k+1)k^2>(2k+1)^2$, that is, $k^2>2k+1$, which is true for $k>2$.