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$

Question

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.

Answer 1

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.

Answer 2

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.

Answer 3

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$.

Answer 4

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*}