Limit of $\frac{x_{n}}{n}$ if $ x_{n} = \sqrt{{n \over 2} + x_{n - 1}x_{n - 2}\,}$ 
Let real sequence  $\left\{x_{n}\right\}$ such $x_{0} = x_{1} =1$, and
  $$
x_{n} = \sqrt{{n \over 2} + x_{n - 1}x_{n - 2}\,}\,,\qquad n \geq 2\,;\qquad
\mbox{Find}\quad\lim_{n\to\infty}{x_{n} \over n} =\ {\large ?}$$

My try:
$\displaystyle{\mbox{Since}\quad
\left(~x^{2}_{n} = {n \over 2} + x_{n - 1}x_{n - 2}
\quad\Longrightarrow\quad 2x^{2}_{n} = n + 2x_{n - 1}x_{n - 2}~\right)}$
and I know this $x_{n}$ don't have simple form. I guess 
$\displaystyle{\lim_{n\to \infty}{x_{n} \over n} = {\sqrt{6} \over 6}}$. So I ask: How find this limit is $\displaystyle{\sqrt{6} \over6}$ ?. Then I can't. Thank you.  very much!
 A: To identify the limit if one assumes it exists, and even a little more, is easy--but should not be taken for a proof that $x_n/n$ converges.
To wit, assume that a property stronger than the convergence of $x_n/n$ holds, namely, that $x_{n+1}-x_n$ converges to some nonzero limit $\ell$ (when this happens, $\ell$ is also the limit of $x_n/n$). 
Then $x_{n-1}=x_n-\ell+o(1)$ and $x_{n-2}=x_n-2\ell+o(1)$ hence 
$x_{n-1}x_{n-2}=x_n^2-3\ell x_n+o(x_n)$. 
By identification $3\ell x_n\sim\frac12n$. Since $x_n\sim\ell n$, 
$3\ell^2=\frac12$ hence $\ell=\frac1{\sqrt6}$.
Once again, this is not a proof that $x_n/n$ converges (and does not use the initial condition $x_0=x_1=1$).
A: Show that
$$
\frac{n}{\sqrt{6}} \leq x_n \leq \frac{n}{\sqrt{6}} + 1
$$
by induction.

To guess this inequality I performed an analysis similar to Did's.  I substituted
$$
x_n = an + b + o(1)
$$
into the recurrence and found it to be consistent when
$$
a = \frac{1}{\sqrt{6}},
$$
and
$$
b = \frac{1}{3} \sqrt{\frac{2}{3}} \approx 0.27,
$$
so it would be reasonable to expect that
$$
x_n = \frac{n}{\sqrt{6}} + \frac{1}{3} \sqrt{\frac{2}{3}} + o(1).
$$
Based on this, I guessed that the inequalities
$$
x_n \geq \frac{n}{\sqrt{6}} \qquad \text{and} \qquad x_n \leq \frac{n}{\sqrt{6}} + x_0 = \frac{n}{\sqrt{6}} + 1
$$
might hold, which I then verified by induction.
In fact, this analysis suggests the tighter inequality
$$
\frac{n}{\sqrt{6}} + \frac{1}{3} \sqrt{\frac{2}{3}} \leq x_n \leq \frac{n}{\sqrt{6}} + 1,
$$
which can also be shown by induction.
