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”

alternative-proofconvergence-divergenceproof-verificationreal-analysis

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 <x_{2n+1} < \cdots <x_5<x_3<x_1$$

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$.

Best Answer

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.

Related Question