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.
 A: Generalizing,
consider
$a_{n+1} 
= a_n + \dfrac{n^c}{a_n}
$
where
$c > 0$
and
$a_1 = a > 0$.
I can show that
$a(c+1)\ln(m)+O(1)
\lt a_m
\lt \dfrac{m^{c+1}}{a(c+1)}+O(m^c)
$.
I am pretty sure that
the upper bound
is the correct order of magnitude,
but I can't prove it now.
We have
$a_{n+1} > a_n$
so
$a_{n+1} 
\gt a_n + \dfrac{n^c}{a_{n+1}}
$
so
$\begin{array}\\
a_m-a_1
&=\sum_{n=1}^{m-1} (a_{n+1}-a_n)\\
&=\sum_{n=1}^{m-1}  \dfrac{n^c}{a_n}\\
&\lt\sum_{n=1}^{m-1}  \dfrac{n^c}{a}\\
&=\dfrac1{a}\sum_{n=1}^{m-1}n^c\\
&=\dfrac1{a}(\dfrac{m^{c+1}}{c+1}+O(m^c))\\
\end{array}
$
so
$a_m
\lt a+\dfrac1{a}(\dfrac{m^{c+1}}{c+1}+O(m^c))
= \dfrac{m^{c+1}}{a(c+1)}+O(m^c)
$
and
$\begin{array}\\
a_m-a_1
&=\sum_{n=1}^{m-1}  \dfrac{n^c}{a_n}\\
&\gt\sum_{n=1}^{m-1}  \dfrac{n^c}{\dfrac{n^{c+1}}{a(c+1)}+O(n^c)}\\
&\gt\sum_{n=1}^{m-1}  \dfrac{n^{-1}}{\dfrac{1}{a(c+1)}+O(n^{-1})}\\
&=a(c+1)(\ln(m)+O(1))\\
\end{array}
$
so
$a_m
\gt a(c+1)\ln(m)+O(1)
$.
A: 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}.$$
