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$ – Rene Schipperus Mar 6 '17 at 21:55
  • $\begingroup$ @Rene Schipperus It's my old unsolved problem $\endgroup$ – Michael Rozenberg Mar 6 '17 at 23:05
  • $\begingroup$ Is it solved now ? $\endgroup$ – Rene Schipperus Mar 7 '17 at 1:08
  • $\begingroup$ @ReneSchipperus Yes, it is. $\endgroup$ – Sungjin Kim Mar 7 '17 at 2:11
  • $\begingroup$ Its a difficult problem. Or it was... $\endgroup$ – Rene Schipperus Mar 7 '17 at 3:45
15
$\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$ – Sungjin Kim Mar 7 '17 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$ – Michael Rozenberg Mar 7 '17 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$ – Sungjin Kim Mar 7 '17 at 6:11
  • 1
    $\begingroup$ @ i707107 Why there are these subsequences? $\endgroup$ – Michael Rozenberg Mar 7 '17 at 6:22
  • 1
    $\begingroup$ Bolzano Weierstrass Theorem: Any bounded sequence has a convergent subsequence. $\endgroup$ – Sungjin Kim Mar 7 '17 at 8:16
10
$\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$ – Sungjin Kim Mar 6 '17 at 22:45
  • 4
    $\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$ – Sungjin Kim Mar 7 '17 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.