Prove that $\sqrt{n - 1}\leq u_n \leq \sqrt n$, and find $\lim_{n\rightarrow \infty }\frac{u_n}{\sqrt n}$ Given a $(u_n)$ sequence that has the following recursive formula:
$$\left\{\begin{matrix}
u_1=1
\\
u_{n+1}=\frac{u_n^2+2n}{3u_n}, n \in \mathbb{N}^*
\end{matrix}\right.$$
Prove that $\sqrt{n - 1}\leq u_n \leq \sqrt n$, and find $\lim_{n\rightarrow \infty }\frac{u_n}{\sqrt n}$
The only clue that I have is that the first problem is solved by induction.
 A: One possible simplification to your method would be to let $\sqrt{n}v_n = u_n$, so that your recursion becomes
$$v_{n+1} = \sqrt{n \over n+1}\bigg({v_n \over 3} + {2 \over 3v_n}\bigg)$$
Then you'd have to show that given that $\sqrt{n - 1 \over n} \leq v_n \leq 1$, one has $\sqrt{n \over n + 1} \leq v_{n+1} \leq 1$. I'm not sure that this works, but the function ${x \over 3} + {2 \over 3x}$ is decreasing on the range in question so it should be able to be checked one way or the other.
A: I'm not sure about this but I'll give it a try .I can only find the limit though:
Followed Zarrax's way,as $n$ goes to $\infty$:
$$ v_{n+1}= \frac{v_{n}}{3}+\frac{2}{3v_{n}} $$
Assume $O(v_{n})<O\left(n^0\right)\Rightarrow O\left(\frac{1}{v_{n}}\right)>O\left(n^0\right)\Rightarrow O(v_{n+1})>O\left(n^0\right)$ which is contradictory with our assumption.
Assume $O(v_{n})>O\left(n^0\right)\Rightarrow {v_{n}}$ is increasing but $v_{n+1} \sim \frac{v_{n}}{3}$ means the sequence is decreasing so that’s also contradictory with our assumption.
Hence, $v_{n} \sim O\left(n^0\right)$ and $\lim \limits_{n\to\infty} \frac{u_{n}}{\sqrt{n}}$ exists.
We got  $v_{n+1}=v_{n}$, now we solve for $v_n$(as limit): $\frac{v_n}{3}+\frac{2}{3v_n}=v_n \Rightarrow v_n=1$
Conclusion: $\lim \limits_{n\to\infty} \frac{u_n}{\sqrt{n}}= 1$
A: As OP showed in the comments, the naive induction hypothesis substitution isn't sufficient to tighten the bounds, because we're using different values for $ u_n$ which makes the bounds too loose.
As it turns out, all that we need to do, is to use the same value in the numerator and denominator.
Claim: For $n\geq 2$,  $ \sqrt{n-1} \leq x \leq \sqrt{n} $, then $\sqrt{ n} \leq \frac{x^2 + 2n } { 3x } \leq \sqrt{n+1}$.

 Show that the turning point is $\pm \sqrt{2n}$, so the graph is decreasing over the domain.
 Hence, we just have to check the endpoints.


 Clearly $ \sqrt{n} \leq \frac{ 3n}{3 \sqrt{n}} $ establishes the LHS.


 Show that for $ n > 5/3$, $\frac { 3n-1 } { 3\sqrt{n-1}} \leq \sqrt{n+1}$ which establishes the RHS.

Can you complete this from here?

*

*Prove the claim.

*Show how the claim implies problem 1.

*Show how problem 1 implies the answer to problem 2.

A: So I think I may have solve the first problem?
Not really sure whether this works or not, highly appreciate if someone can point out any error in my solution.
Still using induction, even though I heard that this can be solved by transforming into explicit formula.
With $n=1$: $\sqrt{1-1}=0\leq u_1=1 \leq \sqrt{1} = 1$. So it's true for $n=1$.
Assume that it's true for $n=k, k \geq 2$, or $\sqrt{k-1}\leq u_k \leq \sqrt{k}$.
We have: $$u_{k+1}=\frac{u_k^2+2k}{3u_k} \geq \sqrt{k} \geq u_k\Leftrightarrow 2k \geq 2u_k^2 \Leftrightarrow u_k \leq \sqrt{k}$$
Which is true.
We also have:$$u_{k+1}=\frac{u_k^2+2k}{3u_k} \leq \sqrt{k+1} \leq \sqrt{u_k^2+2}\Leftrightarrow 8u_k^4+18u_k^2-4u_k^2k-4k^2\geq0$$
We can see that: $$8u_k^4+18u_k^2-4u_k^2k-4k^2\geq6k-10\geq0, \forall k \geq 2$$
So it's true for $n=k+1$. And according to mathematical induction, it's true $\forall n \geq 1$.
Edit:
I got my hands on the actual solution, and it's surprisingly simple.
The first solution is solved by derivative and induction.
With $n=1, n=2$, it's true so I'll skip this part.
Assume that it's true for $n=k, k \geq 2$, or $\sqrt{k-1}\leq u_k \leq \sqrt{k}$.
Consider the following function: $$f(x)=\frac{x^2+2k}{3x}$$
We have the derivative:
$$f'(x)=\frac{1}{3}-\frac{2k}{3x^2}, x\in[\sqrt{k-1}; \sqrt{k}]$$
Using the naive way inequality substitution we will have:
$$-\frac{1}{3}\leq f'(x) < 0$$
So the function is antitone $\forall x\in[\sqrt{k-1}; \sqrt{k}]$.

*

*$$u_k \leq \sqrt{k} \Rightarrow f(u_k) \geq f(\sqrt{k}) \Leftrightarrow u_{k+1} \geq \sqrt{k}$$
2.1.  $$u_k \geq \sqrt{k-1} \Rightarrow f(u_k) \leq f(\sqrt{k-1}) \Leftrightarrow u_{k+1} \leq \frac{3k-1}{3\sqrt{k-1}}$$
2.2.  $$\frac{3k-1}{3\sqrt{k-1}} \leq \sqrt{k+1} \Leftrightarrow k \geq \frac{5}{3}$$
Which is true.
So it's true for $n=k+1$. And according to mathematical induction, it's true $\forall n \geq 1$.
The second problem is solved by the sandwich theorem.
We have: $$\sqrt{n-1}\leq u_n \leq \sqrt{n} \Leftrightarrow \sqrt{1-\frac{1}{n}} \leq \frac{u_n}{\sqrt{n}} \leq 1 \Leftrightarrow \lim_{n\rightarrow +\infty}\sqrt{1-\frac{1}{n}} \leq \lim_{n\rightarrow +\infty}\frac{u_n}{\sqrt{n}} \leq 1$$
And we have: $$\lim_{n\rightarrow +\infty}\sqrt{1-\frac{1}{n}} = 1$$
So according to the sandwich theorem: $$\lim_{n\rightarrow +\infty}\frac{u_n}{\sqrt{n}} = 1$$
