# A shorter proof for the theorem “For $x_0,a \in \mathbb R^+$, the sequence $(x_n)$ defined by $x_{n+1}=a/(1+x_n)$ is convergent”

I'm doing Problem II.4.5 in textbook Analysis I by Amann/Escher.

For $$x_0,a \in \mathbb R^+$$, the sequence $$(x_n)_{n \in \mathbb N}$$ defined recursively by $$x_{n+1}=a/(1+x_n)$$ is convergent.

My questions:

1. Could you please verify whether my attempt on is fine or contains logical gaps/errors? Any suggestion is greatly appreciated!

2. I feel that my proof is too long. I would like to ask for a simpler one.

Thank you so much!

My attempt:

First we consider the case $$x_0 < x_1$$.

Lemma 1: $$x_{m+1} < x_{n+1}$$ if and only if $$x_m > x_n$$ for all $$m,n$$.

Proof: We have $$x_{m+1} < x_{n+1} \iff a/(1+x_m) < a/(1+x_m) \iff x_m > x_n$$.

Lemma 2: $$x_{2n} < x_{2n+1}$$ for all $$n$$.

Proof: The statement trivially holds for $$n=0$$. Let it hold for some $$n$$. We have \begin{aligned} x_{2(n+1)} < x_{2(n+1)+1} & \iff x_{2n+2} < x_{2n+3} \\ &\overset{(\star)}{\iff} x_{2n+1} > x_{2n+2} \\ &\overset{(\star\star)}{\iff} x_{2n} < x_{2n+1} \quad (\star\star\star)\end{aligned} in which $$(\star)$$ and $$(\star\star)$$ follow from Lemma 1, $$(\star\star\star)$$ follows from inductive hypothesis. As such, the statement holds for $$n+1$$.

Lemma 3: $$x_{2n} < x_{2n+2}$$ for all $$n$$.

Proof: We have $$x_2 = a/(1+x_1) = a/(1+a/(1+x_0))$$. So $$x_2 > x_0 \iff a/x_0 >$$ $$1+a/(1+x_0) \iff a/(x_0(1+x_0)) > 1 \iff a/(1+x_0) > x_0 \iff x_1 > x_0$$. As such, the statement holds for $$n=0$$. Let it hold for some $$n$$. We have \begin{aligned} x_{2(n+1)} < x_{2(n+1)+2} & \iff x_{2n+2} < x_{2n+4} \\ &\overset{(\star)}{\iff} x_{2n+1} > x_{2n+3} \\ &\overset{(\star\star)}{\iff} x_{2n} < x_{2n+2} \quad (\star\star\star)\end{aligned} in which $$(\star)$$ and $$(\star\star)$$ follow from Lemma 1, $$(\star\star\star)$$ follows from inductive hypothesis. As such, the statement holds for $$n+1$$.

It follows from Lemma 3 that $$(x_{2n})_{n \in \mathbb N}$$ is an increasing sequence.

Lemma 4: $$x_{2n+3} < x_{2n+1}$$ for all $$n$$.

Proof: $$x_{2n+3} < x_{2n+1} \overset{(\star)}{\iff} x_{2n+2} > x_{2n} \quad (\star\star)$$ in which $$(\star)$$ follow from Lemma 1 and $$(\star\star)$$ follows from Lemma 3.

It follows from Lemma 4 that $$(x_{2n+1})_{n \in \mathbb N}$$ is a decreasing sequence.

Lemma 5: $$x_0 < x_{2n+1}$$ for all $$n$$.

Proof: We have $$x_0 \overset{(\star)}{\le} x_{2n} \overset{(\star\star)}{<} x_{2n+1}$$ in which $$(\star)$$ follows from the fact that $$(x_{2n})_{n \in \mathbb N}$$ is increasing, and $$(\star\star)$$ follows from Lemma 2.

Lemma 6: $$x_{2m} < x_{2n+1}$$ for all $$m,n$$.

Proof: The statement holds for $$m=0$$ from Lemma 5. Let it hold for some $$m$$. We have \begin{aligned} x_{2(m+1)} < x_{2n+1} & \iff x_{2m+2} < x_{2n+1} \\ &\overset{(\star)}{\iff} x_{2m+1} > x_{2n} \quad (\star\star)\end{aligned}

Statement $$(\star\star)$$ holds for $$n=0$$ from Lemma 5. For $$n \ge 1$$ and from Lemma 1, statement $$(\star\star)$$ is equivalent to $$x_{2m} < x_{2n -1} = x_{2(n-1)+1}$$, which is true by inductive hypothesis. As such, the statement holds for $$m+1$$.

From Lemmas 3,4, and 6, our sequence $$(x_n)_{n \in \mathbb N}$$ looks like $$x_0 < x_2 < x_4 < \cdots < x_{2n}< \cdots

By Nested Intervals Theorem, we have $$\lim_{n \to \infty}x_{2n} = \sup_{n \in \mathbb N} x_{2n} =:\alpha = \inf_{n \in \mathbb N} x_{2n+1} = \lim_{n \to \infty}x_{2n+1}$$

Next we prove that $$\lim_{n \to \infty}x_{n} = \alpha$$

Approach 1: For $$\varepsilon > 0$$, there exists $$N \in \mathbb N$$ such that $$|x_{2n} - \alpha| < \varepsilon$$ and $$|x_{2n+1} - \alpha| < \varepsilon$$ for all $$n > N$$. Thus $$|x_{n} - \alpha| < \varepsilon$$ for all $$n > 2N$$. As a result, $$\lim_{n \to \infty}x_{n} = \alpha$$.

Approach 2:

Given $$n \in \mathbb N$$, we have $$A := \{2k+1 \in \mathbb N \mid k \ge n\} \subseteq B := \{k \in \mathbb N \mid k \ge n\}$$ and, for each $$k \in B$$, there exists $$k' \in A$$ such that $$x_k \le x_{k'}$$. As such, $$\sup_{k \ge n} x_{k} = \sup_{k \ge n} x_{2k+1}$$ and thus $$\inf_{n \ge 0} \sup_{k \ge n} x_{k} = \inf_{n \ge 0} \sup_{k \ge n} x_{2k+1}$$. Similarly, we have $$\sup_{n \ge 0} \inf_{k \ge n} x_{2k} = \sup_{n \ge 0} \inf_{k \ge n} x_{k}$$. It follows that $$\alpha = \sup_{n \ge 0} \inf_{k \ge n} x_{2k} = \sup_{n \ge 0} \inf_{k \ge n} x_{k} \le \inf_{n \ge 0} \sup_{k \ge n} x_{k} = \inf_{n \ge 0} \sup_{k \ge n} x_{2k+1} = \alpha$$ and thus $$\lim_{n \to \infty} x_{n} = \alpha$$.

The case $$x_0 > x_1$$ is similar, while the case $$x_0 = x_1$$ is trivial.

Update: @LutzL pointed out the lack the proof $$\lim_{n \to \infty}x_{2n} = \lim_{n \to \infty}x_{2n+1}$$, which is a critical gap in my attempt. I added that part here. Thank you so much for carefully reading my attempt @LutzL ;) I wish I could upvote your answer more and more.

We define the sequence $$(y_n)$$ by $$y_n := x_{2n+1} - x_{2n}$$. We have \begin{aligned}y_{n+1} &= x_{2(n+1)+1} - x_{2(n+1)} &&= x_{2n+3} - x_{2n+2}\\ &= \dfrac{a}{1+ x_{2n+2}} - \dfrac{a}{1+ x_{2n+1}} && \overset{(\star)}{\le} \dfrac{a}{1+ x_{2n}} - \dfrac{a}{1+ x_{2n+1}} \\ &= \dfrac{a(x_{2n+1} - x_{2n})}{(1+ x_{2n})(1+ x_{2n+1})} && \overset{(\star\star)}{=} \dfrac{x_{2n+1}}{1+ x_{2n+1}} y_{n} \\ & \overset{(\star\star\star)}{\le} \dfrac{x_{1}}{1+ x_{1}} y_n \end{aligned} in which $$(\star)$$ follows from $$x_{2n+2} \ge x_{2n}$$ (Lemma 3), $$(\star\star)$$ follows from $$a/(1+x_{2n}) = x_{2n+1}$$ and $$x_{2n+1} - x_{2n} = y_n$$, and $$(\star\star\star)$$ follows from $$x_{2n+1} < x_1$$ (Lemma 4).

Let $$\beta := \dfrac{x_{1}}{(1+ x_{1})} < 1$$. Then $$y_{n+1} \le \beta y_n$$ and thus $$y_{n} \le \beta^n y_0$$ for all $$n$$.

We have $$0 \le \lim_{n \to \infty} y_n \le \lim_{n \to \infty} \beta^n y_0 = 0$$. As such, $$\lim_{n \to \infty} y_n = 0$$ and so $$\lim_{n \to \infty}x_{2n} = \lim_{n \to \infty}x_{2n+1} = \alpha$$.

• How did you conclude that $\sup x_{2n}=\inf x_{2n+1}$? It is not wrong, and easy to check that both limits satisfy the same quadratic equation $x=\frac{a(x+1)}{x+1+a}$, but I did not see that argument. – LutzL Aug 14 at 11:59
• Hi @LutzL, thank you so much for pointing out my critical gap. I will work on it after dinner ;) – Le Anh Dung Aug 14 at 13:10

## Alternative approach

If you represent the iterates $$x_k$$ as fractions $$p_k/q_k$$, then you have some freedom in assigning the iteration of numerator and denominator in $$\frac{p_{k+1}}{q_{k+1}}=\frac{aq_k}{p_k+q_k}.$$ Choose to make the separate iterations linear, $$\pmatrix{p_{k+1}\\q_{k+1}} = \pmatrix{0&a\\1&1}\pmatrix{p_k\\q_k}.$$ The iteration matrix has characteristic polynomial $$0=λ^2-λ-a$$ with roots $$λ_{1,2}=\frac12(1\pm\sqrt{1+4a})$$ and eigenvectors $$\pmatrix{a\\λ_k}$$ for eigenvalue $$λ_k$$. Then the explicit solution for the iteration is $$x_k=a\frac{c_1λ_1^k+c_2λ_2^k}{c_1λ_1^{k+1}+c_2λ_2^{k+1}} =a\frac{c_1+c_2(λ_2/λ_1)^k}{c_1λ_1+c_2λ_2(λ_2/λ_1)^k}$$ This converges to $$\frac{a}{λ_1}=-λ_2=\frac12(\sqrt{1+4a}-1)$$ as $$|λ_2/λ_1|<1$$.

## Comments on the proof in the question

Now that your proof is complete (up to a remark about the index shift $$\tilde x_k=x_{k+1}$$ in the case $$x_0>x_1$$), there is not much you can do to make it shorter and keep the same level of detail. What can be done to make it a little more structured and possibly shorter is to put the two-step iteration $$x_{n+2}=\frac{a(x_n+1)}{x_n+1+a}=a-\frac{a^2}{x_n+1+a}$$ more into focus. From the last form one easily sees that this relation is a monotonically increasing function. It follows directly that the odd-index and even-index subsequences have to be monotonous, falling or increasing. Together with your first two lemmas for their mutual boundedness it follows that they converge. The limits then have to be roots of $$x=\frac{a(x+1)}{x+1+a}\iff x^2+x-a=0,$$ and as this has only one positive root, both limits are the same.

Now if you have a complete partition of a sequence into sub-sequences, and all of these sub-sequences have the same limit, then the original sequence converges, with this same limit.

• Hi @LutzL, I'm grateful that you pointed out my critical gap $\sup x_{2n}=\inf x_{2n+1}$ in my attempt. After several hours of thinking, I have figured a proof and added it as an update in my question. Could you please have a check on my update? – Le Anh Dung Aug 15 at 7:13
• Honestly, I'm only at the point about convergence in my textbook. Your solution is simple (and thus elegant), but I could not understand it at this time ^^. – Le Anh Dung Aug 15 at 7:16
• Added section summarizing my remaining comments – LutzL Aug 15 at 8:06
• Thank you so much for your very detailed answer :) – Le Anh Dung Aug 15 at 8:08