12
$\begingroup$

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!

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

2 Answers 2

14
$\begingroup$

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.

$\endgroup$
6
  • 1
    $\begingroup$ 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. $\endgroup$ Mar 7, 2017 at 6:03
  • 1
    $\begingroup$ Yes, you are right! I am wrong. Now I don't understand, why $a\leq\frac{2+a}{2+b}$ $\endgroup$ Mar 7, 2017 at 6:08
  • 1
    $\begingroup$ 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. $\endgroup$ Mar 7, 2017 at 6:11
  • 1
    $\begingroup$ @ i707107 Why there are these subsequences? $\endgroup$ Mar 7, 2017 at 6:22
  • 1
    $\begingroup$ Bolzano Weierstrass Theorem: Any bounded sequence has a convergent subsequence. $\endgroup$ Mar 7, 2017 at 8:16
9
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ After playing around with Excel, the sequence does not look like monotone. $\endgroup$ Mar 6, 2017 at 22:45
  • 5
    $\begingroup$ 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.$ $\endgroup$ Mar 7, 2017 at 3:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.