<s>[INST] How does $a_{n+1} = a_n + \frac{n^2}{a_n}$ grow? Let $\{a_n\}$ be a positive sequence such that $a_{n+1} = a_n + \frac{n^2}{a_n}$. What is the rate of growth of $a_n$?
I have seen this similar question which deals with $a_{n+1} = a_n + \frac{n^{1/2}}{a_n}$, but I am not sure how to apply that theorem of Cesaro-Stolz here.
 [/INST] The answer is now completely reviewed thanks to Gary's useful comments.

*

*First note that
$$a_{n+1} = f_n(a_n)$$ where
$$f_n(x) = x + \frac{n^2}x\geq 2n,$$
for $x>0$, so that $$a_{n}\geq 2(n-1)\geq n,\tag{1}\label{1}$$
for $n\geq 2$, and the sequence is divergent.

*Now observe that $$a_{n+1}^2 = a_n^2\left(1+\frac{n^2}{a_n^2}\right)^2,$$ so that letting $b_n = a_n^2$ yields
$$b_{n+1} = g_n(b_n),$$
where
$$g_n(x) = x\left(1+\frac{n^2}x\right)^2.$$
The above function is monotonically increasing for $x\geq n^2$, and has slant asymptote $$h_n(x) = x + 2n^2.$$ The distance $g_n(x)-h_n(x)=\frac{n^4}x$ is positive and monotonically decreasing.

*Iterating on $n$ the inequality $$b_{n+1}\geq b_n + 2n^2,$$ valid, by \eqref{1}, for $n\geq 2$ we obtain that
$$b_{n+1} \geq b_2 -2 + 2\frac{n(n+1)(2n+1)}6\geq \frac{2n^3}3$$

*Using 2. we have, for large enough $n$, \begin{eqnarray}0\leq b_{n+1}-b_n-2n^2&=&g_n(b_{n})-h_n(b_n)\leq g_n\left(\frac{2(n-1)^3}3\right)-h_n\left(\frac{2(n-1)^3}3\right)\leq \\
&\leq&\frac{3n^4}{2(n-1)^3}\leq 3n.\end{eqnarray}

*From 4., thus, we get $$b_n + 2n^2 \leq b_{n+1}\leq b_n + 2n^2 + 3n.$$ Iterating on $n$ yields $$b_2 -5 + \frac{n(n-1)(2n-1)}3 \leq b_n \leq b_2 -5 + \frac{n(n-1)(2n-1)}3 + \frac{3n(n-1)}2,$$
and by the Squeeze Theorem $$b_n \sim \frac23 n^3.$$
Hence $$a_n \sim \sqrt{\frac23} n^{3/2}.$$
</s>