# Limit of a sequence defined by a two-step nonlinear recursion

Let $x_0, x_1$ be positive numbers and define $$x_{n+2}=x_{n+1}+\frac{1}{x_n + \sqrt{n}}$$

Prove that the sequence $y_n = x_n / \sqrt{n} \to 1 \\ \\ \\$.

My attempt:

I think it would suffice to consider the inequalities $x_n < \sqrt{n}$ and $x_n > \sqrt{n}$. From the given recursion, we would then extract $$x_{n+2} - x_{n+1} = \frac{1}{x_n + \sqrt{n}} > \frac{1}{2\sqrt{n}}$$ (flip the inequality in the other case) and compute $y_n$ from this. But the issue here is that I can't find the necessary limit in both cases.

• Just an observation so far: The process itself does not necessarily move closer to $\sqrt{n}$ in either relative or absolute terms. Take $x_0 = 2$ and $x_1=0.15$. $\;x_n$ starts below $\sqrt{n}$ but exceeds it before approaching it from above, $\dfrac{x_n}{\sqrt{n}}$ does not begin consistently approaching $1$ until $n=11$, and $x_n - \sqrt{n}$ does not begin consistently approaching $0$ until $n=46$. – Neil W Apr 29 '14 at 12:56

$$\limsup_{n\to \infty}\frac{x_n}{\sqrt{n}}\le \limsup_{n\to \infty}\frac{x_n-x_{n-1}}{\sqrt{n}-\sqrt{n-1}}=2\cdot\limsup_{n\to \infty}\sqrt{n}(x_n-x_{n-1}),\tag{1}$$ and $$\liminf_{n\to \infty}\frac{x_n}{\sqrt{n}}\ge \liminf_{n\to \infty}\frac{x_n-x_{n-1}}{\sqrt{n}-\sqrt{n-1}}=2\cdot\liminf_{n\to \infty}\sqrt{n}(x_n-x_{n-1}).\tag{2}$$ By the definition of $(x_n)$,
$$\limsup_{n\to \infty}\sqrt{n}(x_n-x_{n-1})=\limsup_{n\to \infty}\frac{\sqrt{n}}{x_{n-2}+\sqrt{n-2}}=\frac{1}{\liminf\limits_{n\to \infty}\frac{x_n}{\sqrt{n}} +1},\tag{3}$$ and
$$\liminf_{n\to \infty}\sqrt{n}(x_n-x_{n-1})=\liminf_{n\to \infty}\frac{\sqrt{n}}{x_{n-2}+\sqrt{n-2}}=\frac{1}{\limsup\limits_{n\to \infty}\frac{x_n}{\sqrt{n}} +1}.\tag{4}$$ From $(1)$ and $(3)$ we know that $$\limsup_{n\to \infty}\frac{x_n}{\sqrt{n}}\left(\liminf_{n\to \infty}\frac{x_n}{\sqrt{n}} +1\right) \le 2,\tag{5}$$ and from $(2)$ and $(4)$ we know that $$\liminf_{n\to \infty}\frac{x_n}{\sqrt{n}}\left(\limsup_{n\to \infty}\frac{x_n}{\sqrt{n}} +1\right) \ge 2.\tag{6}$$ Comparing $(5)$ with $(6)$, we can conclude that $$\limsup_{n\to \infty}\frac{x_n}{\sqrt{n}}=\liminf_{n\to \infty}\frac{x_n}{\sqrt{n}}=1.$$
• How do you know that $$\limsup_{n\to \infty}\frac{x_n-x_{n-1}}{\sqrt{n}-\sqrt{n-1}}=2\cdot\limsup_{n\to \infty}\sqrt{n}(x_n-x_{n-1})$$? – user41281 Sep 12 '14 at 17:52