Prove that if $x_{n+2}=\frac{2+x_{n+1}}{2+x_n},$ then $x_n$ converges

Let $x_0 > 0$, $x_1 > 0$ and $$x_{n+2} = \dfrac{2+x_{n+1}}{2+x_n}$$ for $n \in \{0,1,\dots\}$. Prove that $x_n$ converges.

My attempt:

If $x_n$ converges and $\lim\limits_{n\rightarrow\infty}x_n=a$ so $a=\frac{2+a}{2+a}$, which gives $a=1$. Now,

$$x_{n+2}-1=\frac{x_{n+1}-x_n}{2+x_n}$$

and what is the rest? Thank you!

• Where did you find this problem ? Mar 6, 2017 at 21:55
• @Rene Schipperus It's my old unsolved problem Mar 6, 2017 at 23:05
• Is it solved now ? Mar 7, 2017 at 1:08
• @ReneSchipperus Yes, it is. Mar 7, 2017 at 2:11
• Its a difficult problem. Or it was... Mar 7, 2017 at 3:45

Proof of Convergence

By @Integral's answer, the sequence is bounded (by $0$ from below for all $n$, and $x_0+2$ from above when $n\geq 2$). An alternative argument (using $x_{n+3}$, it is bounded above by $3/2$ when $n\geq 3$) to prove boundedness is provided as a comment to @Integral's answer.

We have finite $a=\limsup x_n$ and $b=\liminf x_n$. For the definition of $\limsup x_n$ and $\liminf x_n$, see limit superior / limit inferior. See also Bolzano-Weierstrass Theorem which states that any bounded sequence has a convergent subsequence.

By the recurrence, we have the following:

$$a\leq \frac{2+a}{2+b}, \ \ b\geq \frac{2+b}{2+a}. \ \ \ (*)$$

Since $a\geq b\geq 0$, we obtain $$2a+ab\le 2+a, \ \ 2b+ab \geq 2+b.$$ These yield $$a\leq 2-ab, \ \ b\geq 2-ab.$$ Then we obtain the inequality $a\leq 2-ab \leq b$. This is the reverse inequality of $a\geq b$. Therefore, we have $a=b$. Hence, the sequence converges.

Proof of (*)

Take a subsequence $\{x_{n_k}\}$ such that $x_{n_k} \rightarrow a$ as $k\rightarrow\infty$. We have $$x_{n_k} = \frac{2+ x_{n_k-1}}{2+x_{n_k-2}}.$$ Take a further subsequence such that both $\{x_{n_{k_l}-1}\}$ and $\{x_{n_{k_l}-2}\}$ converge. This is possible by Bolzano-Weierstrass Theorem. Then we have

$$x_{n_{k_l}} = \frac{2+ x_{n_{k_l}-1} }{2+x_{n_{k_l}-2}}.$$ Taking limits $l\rightarrow\infty$ both sides, there exist $c$, $d$ with $b\leq c\leq a$, $b\le d\le a$ such that $$\lim_{l\rightarrow\infty} x_{n_{k_l}-1} = c, \ \lim_{l\rightarrow\infty}x_{n_{k_l}-2}=d, \ \ \textrm{ so that } \ a=\frac{2+c}{2+d}.$$ Then replacing $c$ by $a$ and $d$ by $b$, we have the inequality $a\leq \frac{2+a}{2+b}$. The inequality for $b$ follows by the same argument. This time, take $\{x_{m_k}\}$ such that $x_{m_k}\rightarrow b$ instead. Further subsequences $\{x_{m_{k_l}-1}\}$ and $\{x_{m_{k_l}-2}\}$ converge to $c'$ and $d'$ respectively, they satisfy $b\le c' \le a$ and $b\le d' \le a$. From $b=\frac{2+c'}{2+d'}$, replace $c'$ by $b$ and $d'$ by $a$. Then $b\geq \frac{2+b}{2+a}$ follows.

• If you let $\lim\limits_{k\rightarrow\infty} x_{n_k} = a$, it does not follow that $\lim\limits_{k\rightarrow\infty} x_{n_k-1} =a$ nor $\lim\limits_{k\rightarrow\infty} x_{n_k-2} =a$. This is why I had to use the inequalities. Mar 7, 2017 at 6:03
• Yes, you are right! I am wrong. Now I don't understand, why $a\leq\frac{2+a}{2+b}$ Mar 7, 2017 at 6:08
• Because $b$ is the $\inf$ of all subsequential limits, and $a$ is the $\sup$ of all subsequential limits. This is by making denominator smallest possible and numerator largest possible. For more details, let $\lim\limits_{k\rightarrow\infty}x_{n_k} =a$ and take further subsequences of $\{ x_{n_k}\}$ such that $\{ x_{n_{k_l} -1} \}$ and $\{ x_{n_{k_l} -2} \}$ converge. Mar 7, 2017 at 6:11
• @ i707107 Why there are these subsequences? Mar 7, 2017 at 6:22
• Bolzano Weierstrass Theorem: Any bounded sequence has a convergent subsequence. Mar 7, 2017 at 8:16

Clearly every $x_n$ is positive. With this we know that $$x_{n+2} = \frac{2 + x_{n+1}}{2 + x_n} = \frac{2}{2+x_n} + \frac{x_{n+1}}{2+x_n} < 1 + \frac{x_{n+1}}{2}.$$

Applying this recursively we get $$x_n < 1 + \frac{x_{n-1}}{2} < 1 + \frac{1 + \frac{x_{n-2}}{2}}{2} = 1 + \frac{1}{2} + \frac{x_{n-2}}{4} <$$ $$< 1 + \frac{1}{2} + \frac{1 + \frac{x_{n-3}}{2}}{4} = 1 + \frac{1}{2} + \frac{1}{4} + \frac{x_{n-3}}{8} < \frac{x_{n-k}}{2^k} + \sum_{i=0}^{k-1} \frac{1}{2^i}.$$

This bound is valid for any $k = 1 \ldots n$. For $k = n$ we get $$x_n < \frac{x_0}{2^n} + \sum_{i=0}^{n-1} \frac{1}{2^i} < \frac{x_0}{2^n} + 2.$$

Edit: This proves the sequence is bounded. But to get convergence we still need to prove something else, like it is monotone.

• After playing around with Excel, the sequence does not look like monotone. Mar 6, 2017 at 22:45
• An alternative way to prove boundedness is as follows:$$x_{n+3} = \frac1{2+x_n} + \frac2{2+x_{n+1}},$$ From this, $x_{n+3} \le \frac12 + \frac 22 = \frac 32.$ Mar 7, 2017 at 3:20