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
We have:
$$a_{n+1}-1 = \frac{1}{2}\frac{(a_n-1)^2}{a_n}$$
$$a_{n+1}+1 = \frac{1}{2}\frac{(a_n+1)^2}{a_n}$$
Hence
$$\frac{a_{n+1}-1}{a_{n+1}+1}=\left( \frac{a_{n}-1}{a_{n}+1} \right)^2$$
We deduce that
$$\frac{a_{n}-1}{a_{n}+1} = \left( \frac{a_{1}-1}{a_{1}+1} \right)^{2^{n-1}}$$
or the closed form expression of $a_n$
$$a_n =\frac{1-\left( \frac{a_{1}-1}{a_{1}+1} \right)^{2^{n-1}}}{1+\left( \frac{a_{1}-1}{a_{1}+1} \right)^{2^{n-1}}}$$
Best Answer
You can prove by induction on $n$ that $$ n \le a_n \le n + a_1 . $$ Indeed, for $n=1$, these inequalities hold. To move from $n$ to $n+1$, note that $$ a_{n + 1} \ge \sqrt {n \cdot n + 2n + 1} = \sqrt {(n + 1)^2 } = n + 1 $$ and \begin{align*} a_{n + 1} & \le \sqrt {n(n + a_1 ) + 2n + 1} = \sqrt {(n + 1)^2 + na_1 } \\ & \le \sqrt {(n + 1)^2 + 2(n + 1)a_1 + a_1^2 } = n + 1 + a_1 . \end{align*}