Given a recursion $a_{n+ 1}= \sqrt{na_{n}+ 2n+ 1}$ with $a_{1}\geq 1.$ Prove that $a_{n}\sim n\,{\rm as}\,n\rightarrow\infty$ 
Given a recursion $a_{n+ 1}= \sqrt{na_{n}+ 2n+ 1}$ with $a_{1}\geq 1.$ Prove that
$$a_{n}\sim n\,{\rm as}\,n\rightarrow\infty$$

Let $b_{n}= \dfrac{a_{n}}{n},$ we need to prove $\lim b_{n}= 1,$ then we find a value $\beta\in\left ( 0, 1 \right )$ satisfying $\left | b_{n+ 1}- 1 \right |\leq\beta\left | b_{n}- 1 \right |$ so that
$$\beta\rightarrow 0\,{\rm aut}\,n\rightarrow\infty$$
I can't predict the relationship among them, I need the the help to go to the induction, thank you.
 A: You have
$$\begin{aligned}
a_{n+1} &=\sqrt{na_n +2n+1}\\
&= \sqrt{n^2+2n+1+(n a_n -n^2)}\\
&=(n+1) \sqrt{1+\left(\frac{n}{n+1}\right)^2\left(\frac{a_n}{n}-1\right)}
\end{aligned}$$
Hence denoting $b_n =\frac{a_n}{n}$
$$\begin{aligned}
b_{n+1} -1
&=\sqrt{1+\left(\frac{n}{n+1}\right)^2\left(b_n-1\right)}-1
\end{aligned}$$
As for $x\gt 0$
$$\begin{aligned}
\sqrt{1+x}-1 &=\frac{x}{\sqrt{1+x}+1}\\
&\le \frac{1}{2}x
\end{aligned}$$
you get
$$\begin{aligned}0 &\le b_{n+1}-1\\
&\le \frac{1}{2} \left(\frac{n}{n+1}\right)^2 (b_n-1)\\
&\le \frac{1}{2}(b_n-1)
\end{aligned}$$ and can conclude to the desired result.
A: 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*}
A: You don't need $\beta \rightarrow 0$, you just need that for sufficiently large $n$ $$\beta < 1$$ Then $$|b_{n+M}-1|<\beta^n|b_M-1| \rightarrow 0$$
You can check that
$$ b_{n+1} = \sqrt{\frac{b_nn^2 +2n+1}{(n+1)^2}}{} = \sqrt{(b_n-1)\frac{n^2}{(n+1)^2}+1}$$
that is
$$ b_{n+1}-1 = \sqrt{(b_n-1)\frac{n^2}{(n+1)^2}+1} - 1= \frac{(b_n-1)\frac{n^2}{(n+1)^2}}{\sqrt{(b_n-1)\frac{n^2}{(n+1)^2}+1} +1} $$
Since $a_1 \ge 1$, then $b_1 -1 \ge 0$ and by induction it's easy to show that $b_n -1 \ge 0$. We have then
$$ \frac{\frac{n^2}{(n+1)^2}}{\sqrt{(b_n-1)\frac{n^2}{(n+1)^2}+1} +1} \le  \frac{\frac{n^2}{(n+1)^2}}{\sqrt{1}+1} = \frac{n^2}{2(n+1)^2} \le \frac12 $$
Therefore
$$b_{n+1} -1  \le \frac12(b_n-1)$$
As showed before, it is enough to prove that $b_{n+1}-1 \rightarrow 0$.
A: First, from $a_1\ge 1$, one can easily obtain $a_n \ge n$, by induction argument.
Second, using induction again, it is easy to prove that $a_n \le 3a_1n$, for $n\ge 1$.
Hence $1\le b_n \le 3a_1$, where $b_n:=\frac{a_n}{n}$. To show that $a_n \sim n$, it suffices to show $\limsup_{n \rightarrow \infty}b_n\le 1$. Here is the argument:
Fix $N>1$, we have $\frac{N+1}{N}b_{N+1}=\sqrt{b_N+\frac{2N+1}{N^2}}$, and hence $$b_{N+1}<\sqrt{b_N+\frac{3}{N}}\le \sqrt{b_N+\frac{3}{N}b_N}=\left((1+\frac{3}{N})b_N\right)^{1/2}.$$
From iteration, it is easy to see that $$b_{N+k}< \left(1+\frac{3}{N}\right)^{\sum_{i=1}^k1/2^i}b_N^{1/2^k}.$$
Hence from the above, and $b_n \le 3a_1n$, we have that $$\limsup_{n \rightarrow \infty}b_n=\limsup_{k\rightarrow \infty}b_{N+k}<1+3/N.$$
Then let $N\rightarrow \infty$, we have $\limsup_{n\rightarrow \infty}b_n\le 1$. This finishes the proof.
