# If $x_{n+1}=f(x_n)$ and $x_{n+1}-x_n\to 0$, then $\{x_n\}$ converges

Let $f:[0,1] \rightarrow [0,1]$be a continuous function. Choose any point $x_0 \in [0,1]$ and define a sequence recursively by $x_{n+1}=f(x_n)$. Suppose $\lim_{n \rightarrow \infty}x_{n+1}-x_n =0$, does this sequence converge?

• I will add a link to this question, since several answers use this result. – Martin Sleziak Mar 31 '16 at 15:29

The answer is YES - I have fixed the proof of Hongyi:

Let $K$ be the set of sub-sequential limits of the sequence $\{x_n\}$. Then $K$ is compact, and since $x_{n+1}-x_n\to 0$, $K$ is also connected. (This requires some more work.) Hence $K$ is of the form $$K=[a,b]\subset [0,1].$$ If $a=b$, then we are done, since this means that the sequence $\{x_n\}$ has only one sub-sequential limit, and hence converges.

We shall next show that $a<b$ implies that $f(x)=x$ on $[a,b]$, and hence the sequence is eventually constant. This contradicts the fact that its sub-sequential limits are all the points of $[a,b]$.

Assume that $f(x)\not\equiv x$ in $[a,b]$, and let $x_0\in(a,b)$ with $f(x_0)>x_0$. (The case $f(x_0)<x_0$ is treated similarly.) Then there exist $h>0$, such that $$f(x)-x\ge 0\quad\text{whenever}\quad x\in [x_0-h,x_0+h]\subset (a,b).$$ Since $b$ is a limit point of $\{x_n\}$, there exists $x_{n_0}\in (x_0+h,1]$, and the $n_0$ can be picked so that $$\lvert x_{n+1}-x_{n}\rvert <h, \quad \text{when}\quad n\ge n_0.$$ This means that, if $x_{n_0}$ is very close to $b$, then $x_n$, $n\ge n_0$, CAN NOT get smaller than $x_0$, since in the whole interval $[x-h,x+h]$, $f(x_n)\ge x_n$. Thus, $a$ can not be a limit point.

Yes. Let $I = \lim_{k \rightarrow \infty} I_k$ where $I_k$ is the closure of $\{x_k,x_{k+1},...\}$. Note that because $x_{k+1}-x_k \rightarrow 0$, $I$ is connected, thus either a singleton or an interval. If $I$ is a singleton, we are done. If $I$ is an interval $(x_-,x_+)$, then $f(x)=x$ on this interval. It then follows, unless $x_k$ is constant for sufficiently large $k$, that $x_k$ is strictly monotone in $k$; and thus that the sequence must converge to some point within $I$.

• Why is $I$ connected? Why $f(x)=x$ on $I$? – Yiorgos S. Smyrlis Mar 31 '16 at 14:16
• Suppose $I$ isn't connected. Let $x_- = \inf I$ and $x_+ = \sup I$. There must exist some interval $J$ with positive length $j$ within $[x_-,x_+]$ that is disjoint from I. But then since $x_{k+1} - x_k \rightarrow 0$, there must exist some $x_n \in J$, a contradiction; otherwise $\{x_k\}$ cannot "jump" across the interval $J$. – Hongyi Mar 31 '16 at 14:23
• But most important, why is $f(x)=x$ on $I$? – Yiorgos S. Smyrlis Mar 31 '16 at 14:24
• For any $x' \in I$, suppose $f(x') \neq x'$. Let $\{y_1,y_2,...\}$ be a subsequence of $\{x_1,x_2,...\}$ that converges to $x'$. Then $f(y_k) \rightarrow y_k$ because $x_{j+1}-x_j \rightarrow 0$; at the limit, $f(x')=x'$, a contradiction. – Hongyi Mar 31 '16 at 14:35
• (+1) Good work! It is often frustrating that I come up with an answer which is both late and almost identical to the previous ones... – Sangchul Lee Mar 31 '16 at 14:48

I'm fairly sure it need not converge.

Let $$H_n = \sum_{i=1}^n \frac{1}{i}$$

Define $y_n = H_n \pmod{1}$ if $\lfloor H_n \rfloor$ is even, and $1-H_n \pmod{1}$ otherwise. This sequence oscillates between 0 and 1 indefinitely, so it doesn't converge; although $y_{n+1} - y_n$ tends to $0$. It is the case that the difference between distinct harmonic numbers is never an integer, according to Wikipedia, so this sequence never duplicates any value.

We just need to show that we can define continuous $f: [0,1] \to [0,1]$ such that $f(x_n) = x_{n+1}$. I've convinced myself of this with some rather dubious reasoning about infinitesimals.

• While $H_n$ does not duplicate any of its elements, $y_n$ clearly does. But does this matter, anyway? Also, I don't see why $y_{n+1} - y_n \to 0$, it seems more reasonable to say that $y_{n+1} - y_n$ oscillates, too, without having a limit. In fact, your argument seems to be circular. – Alex M. Mar 31 '16 at 14:24
• @Alex M. In order for $f$ to be well-defined in my description, it is necessary that no $y_n = y_m$. Does the sequence $y_n$ ever duplicate an element? – Patrick Stevens Mar 31 '16 at 14:27
• @AlexM. It oscillates without ever converging. Successive terms do get closer and closer together, but the sequence as a whole sways between $0$ and $1$ infinitely often. – Patrick Stevens Mar 31 '16 at 14:28
• No, my mistake, $y_n$ does not duplicate values. I still don't see, though, why $y_{n+1} - y_n \to 0$. – Alex M. Mar 31 '16 at 14:30
• It tends to $0$ because the harmonic series's fractional parts do. By construction, whenever $H_n$ crosses an integer boundary, we start subtracting the fractional part from $1$, so we get $y_{n+1}$ which is once again close to $y_n$. – Patrick Stevens Mar 31 '16 at 14:35