<s>[INST] Estimations of some new recurrence sequences 
Problem 1. Given the recursion $a_{n+ 1}= \sqrt{a_{n}^{2}+ a_{n}}$ with $a_{1}= 1.$ Prove that
$$a_{n}\sim\frac{n}{2}+ \frac{1}{2n}\,{\rm as}\,n\rightarrow\infty$$

For problem 1, I only can prove $a_{n}\sim\left ( n+ 1 \right )/2$ by using the Laurent series for the increasing $a_{n} :$
$$a_{n+ 1}= a_{n}+ \dfrac{1}{2}+ \mathcal{O}\left ( \dfrac{1}{a_{n}} \right )$$

Problem 2. Given the recursion $a_{n+ 1}= \sqrt[3]{a_{n}^{3}+ a_{n}}$ with $a_{1}= 1.$ Prove that
$$a_{n+ 1}\sim\sqrt{\dfrac{2n}{3}}\,{\rm as}\,n\rightarrow\infty$$
What if we changed the given one by $a_{n+ 1}= \sqrt[3]{a_{n}^{3}+ 3a_{n}^{2}+ a_{n}}$ ?

For problem 2, similarly, I saw that $a_{n+ 1}\fallingdotseq a_{n}+ \dfrac{1}{3a_{n}}$, then how can we find the relative equations like ${y}'= \dfrac{1}{3y}$ by $n$ times ?
 [/INST] We may use the approach in [1].
For Problem 1:
First, clearly $\lim_{n\to \infty} a_n = \infty$.
Second, we have
\begin{align}
a_{n+1} - a_n &= \sqrt{a_n^2 + a_n} - a_n\\
&= a_n\left(\sqrt{1 + \frac{1}{a_n}} - 1\right)\\
&= a_n\left(1 + \frac{1}{2} \frac{1}{a_n} 
+ o\left(\frac{1}{a_n}\right) - 1\right)\\
&\to \frac{1}{2},\quad \mathrm{as}\ n\to \infty.
\end{align}
Thus, $a_n \sim \frac{n}{2}$ as $n\to \infty$.
Third, we have
\begin{align}
a_{n+1} - a_n &= \sqrt{a_n^2 + a_n} - a_n\\
&= a_n\left(\sqrt{1 + \frac{1}{a_n}} - 1\right)\\
&= a_n\left(1 + \frac{1}{2} \frac{1}{a_n} - \frac{1}{8}\frac{1}{a_n^2}
+ o\left(\frac{1}{a_n^2}\right) - 1\right)\\
&\sim \frac{1}{2} - \frac{1}{8}\frac{1}{a_n}, \quad \mathrm{as}\ n\to \infty\\
&\sim \frac{1}{2} - \frac{1}{4n}, \quad \mathrm{as}\ n\to \infty.
\end{align}
Thus, $a_n \sim \frac{n}{2} - \frac{1}{4}\ln n$ as $n\to \infty$.
$\phantom{2}$
For problem 2:
First, clearly $\lim_{n\to \infty} a_n = \infty$.
Second, we have
\begin{align}
a_{n+1}^2 - a_n^2 &= (\sqrt[3]{a_n^3 + a_n})^2 - a_n^2 \\
&= a_n^2 \left(\left(1 + \frac{1}{a_n^2}\right)^{2/3} - 1\right)\\
&= a_n^2 \left(1 + \frac{2}{3} \frac{1}{a_n^2} + o\left(\frac{1}{a_n^2}\right) - 1\right)\\
&\to \frac{2}{3}, \quad \mathrm{as}\ n\to \infty.
\end{align}
Thus, $a_n^2 \sim \frac{2}{3}n$ as $n\to \infty$.
Thus, $a_n \sim \sqrt{\frac{2}{3}n}$ as $n\to \infty$.
Reference
[1] "The second term in asymptotic expansion", by Moubinool OMARJEE, Paris
</s>