Limit of $\frac{x_{n}}{n}$ if $ x_{n} = \sqrt{{n \over 2} + x_{n - 1}x_{n - 2}\,}$

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.

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