# Convergence of $x_{n+2} = \sqrt{x_{n+1}} + \sqrt{x_{n}}$

Let $x_0,x_1> 0$. Prove that the sequence defined by $x_{n+2} = \sqrt{x_{n+1}} + \sqrt{x_{n}}$ converges.

Here's my solution: it's easy to prove by induction that $$\forall n, 0<\min(4,u_0,u_1)\leq u_n\leq \max(4,u_0,u_1)$$

The sequence is therefore bounded with $0<\liminf u_n \leq \limsup u_n<\infty$.

By considering a subsequence that converges to $\limsup u_n$, you get two limit points $l_1$ and $l_2$ such that $\limsup u_n = \sqrt{l_1}+\sqrt{l_2}$. Since $\limsup u_n$ is the greatest limit point, this yields $\limsup u_n\leq 2 \sqrt{\limsup u_n}$ which in turn implies $\limsup u_n \leq 4$.

A similar reasoning proves $\liminf u_n \geq 4$, hence $$\liminf u_n = \limsup u_n = 4$$ and the sequence converges to $4$.

Do you know any less advanced proof that an undergraduate might think of ? Preferably something that relies on monotony or an auxillary sequence.

If there is a limit, then $L=2\sqrt{L}$ so that $L=4$. Now $$x_{n+2}-4=\sqrt{x_{n+1}}-2+\sqrt{x_{n}}-2 =\frac{x_{n+1}-4}{\sqrt{x_{n+1}}+2} + \frac{x_{n}-4}{\sqrt{x_{n}}+2}$$ If one can additional prove $x_k\ge 1$ for all $k$ beforehand, then $$|x_{n+2}-4|\le\frac13(|x_{n+1}-4|+|x_{n}-4|)$$
To get a recursive bound, one can try to bound a combined expression of the type \begin{align} |x_{n+2}-4|+a|x_{n+1}-4| &\le \frac{3a+1}3|x_{n+1}-4|+\frac13|x_{n}-4| \\ &\le \frac{b}{3}\left(\frac{(3a+1)}b·|x_{n+1}-4|+\frac1{ab}a|x_{n}-4|\right) \end{align} To finish this bound one needs $a$ and $b$ to satisfy $3a+1\le b$ and $1\le ab$ which is possible for $\frac73\le b<3$ and for $b=\frac73$ requires $a\le\frac49$, $a\ge \frac37$. Using the larger bound results in \begin{align} |x_{n+2}-4|+\frac49|x_{n+1}-4|\le\frac79\left(|x_{n+1}-4|+\frac49·|x_{n}-4|\right) \end{align} giving linear convergence at the geometric rate $\dfrac79$. I.e., $$|x_{n+1}-4|\le |x_{n+1}-4|+\frac49·|x_{n}-4|\le \left(\frac79\right)^n\left(|x_1-4|+\frac49·|x_0-4|\right)$$