$x_{n+1}=f(x_{n})$ converges if and only if $\lim_{n\to \infty}(x_{n+1}-x_{n})=0$

Question

Prove that if $f:[0,1]\rightarrow[0,1]$ is a continuous function, then the sequence of iterates $x_{n+1}=f(x_{n})$ converges if and only if $$\lim_{n\to \infty}(x_{n+1}-x_{n})=0$$

---

First I proved if $x_{n}$ converges then $\lim_{n\to \infty}(x_{n+1}-x_{n})=0$. As $x_n$ converge then, $x_{n+1}$ and $x_n$ converges to the same limit (say $L$), then $\lim_{n\to \infty}(x_{n+1}-x_{n})=L-L=0$. Now we have to prove that if $\lim_{n\to \infty}(x_{n+1}-x_{n})=0$ then $x_n$ converges. Now, for some back calculation, by the continuity of $f$, we can say if $x_n$ does converge to some $X$, then $f(x_n) \rightarrow f(X)=X$, so it converges to a fixed point. And function as it's on $[0,1]\rightarrow[0,1]$ and continuous, so it must have atleast one fixed point. How do I proceed?

Answer 1

Let $K \subseteq [0, 1]$ be the set of all limit points of $(x_n)$, and suppose $\lim_{n\to\infty} (x_{n+1} - x_n) = 0$. We make several observations on $K$:

1. A general theory tells that $K$ is closed. (This is true for any sequence in a metric space.)

2. Every point of $K$ is a fixed point of $f$. Indeed, for each $a \in K$, there exists a subsequence $(x_{n_k})$ that converges to $a$. Hence

   $$ 0 = \lim_{k\to\infty} (x_{n_k + 1} - x_{n_k}) = \lim_{k\to\infty} (f(x_{n_k}) - x_{n_k}) = f(a) - a $$

   and we get $f(a) = a$. In particular, $K$ consists only of fixed points of $f$.

3. $K$ is an interval. Intuitively, suppose $K$ has two distinct points $a$ and $b$. Since the increments of $(x_n)$ becomes smaller as $n$ grows, it will eventually move back and forth between $a$ and $b$ at every decreasing speed. This means that $(x_n)$ will eventually sweep the interval between $a$ and $b$ in a "dense" manner, so every point between $a$ and $b$ will also be a limit point of $(x_n)$.

   Let us implement this idea into a rigorous proof. Let $a = \min K$ and $b = \max K$. (This is possible because $K$ is compact.) Then it suffices to prove that $[a, b] \subseteq K$, or equivalently, every $c \in (a, b)$ lies in $K$. To this end, let $L = b-a$ and choose subsequences $(x_{m_k})$ and $(x_{n_k})$ using the following algorithm:

   • Set $n_0 = 0$ for convenience.
   • Suppose $n_{k-1}$ has been defined. Then choose $m_k$ and $n_k$ so that
     1. $n_{k-1} < m_k < n_k$, and
     2. $|x_{m_k} - a| < L/k$ and $|x_{n_k} - b| < L/k$, and
     3. $|x_{n+1} - x_n| < L/k$ whenever $n \geq m_k$.

   Then we can always find $p_k$ such that $m_k \leq p_k \leq n_k$ and $|x_{p_k} - c| \leq L/k$. Indeed, divide the interval $[a, b]$ into $k$ subintervals of equal length $L/k$. Then by Item 3, each subinterval must contain at least one of the terms in $\{x_{m_k}, \ldots, x_{n_k}\}$. Now pick the one that lies in the subinterval containing $c$ and use that to define $x_{p_k}$. This construction then show that $x_{p_k} \to c$ as $k \to \infty$, hence $c \in K$.

Now we are ready to prove the claim. Suppose $(x_n)$ does not converge. Then $K$ contains at least two elements, hence it is a nondegenerate compact interval. So we may write $K = [a, b]$ for some $a < b$. Then by our observation, $f(x) = x$ for all $x \in [a, b]$. Also, since any interior point of $K$ is a limit point of $(x_n)$, we know that there exists $N$ for which $x_N \in K$. Since $x_N$ is a fixed point of $f$, it then follows that $x_n = x_N$ for all $n \geq N$, hence $(x_n)$ converges. A contradiction!

Answer 2

The essential thing in this problem is to observe that the sequence you have here is a Cauchy Sequence. Why? The proof of forward direction will remains the same as you have pointed out.

The backward direction: Suppose $lim_{n\to \infty} x_{n+1}-x_n = 0$

Then $|x_m-x_n| \leq |x_m-x_{m-1}|+|x_{m-1}-x_{m-2}|+|x_{m-2}-x_{m-3}|+.....+|x_{n+1}-x_n|$ $=|f(x_{m-1})-f(x_{m-2})| + |f(x_{m-2})-f(x_{m-3})|+....+|f(x_{n})-f(x_{n-1})|$ and since $lim_{n\to \infty} x_{n+1}-x_n = 0$ by continuty of $f$ the RHS goes to $0$

This implies that $x_n$ is Cauchy and because $[0,1]$ is compact, $x_n$ converge(Cauchy sequence in compact metric space always converge).

This problem is closely related to Contraction Mapping Theorem. In CMT, the point of having a contraction is to ensure whatever sequence you have will be a Cauchy sequence, hence if your space is complete(in your problem it is), the sequence will converge.

Answer 3

$\lim_{n\to \infty} x_n=L \iff \forall \epsilon>0, \exists N>0 | n>N \implies |x_n-L|<\epsilon/2$

Since $n+1>n>N$, it follows $|x_{n+1}-L| < \epsilon/2$

So $|x_{n+1}-L|+|L-x_n|<2\epsilon \implies |x_{n+1}-x_n|<\epsilon$ by the triangle inequality.

This satisfies the definition of a limit for $\lim_{n \to \infty} x_{n+1}-x_n =0$

But $x_{n+1}=f(x_n)$ so we also have $|f(x_n)-x_n|<\epsilon$ and by hypothesis $x_n \to L$, so we also have $|f(x_n)-L|<\epsilon$, i.e. the definition of convergence of a function.

---

Suppose $\lim_{n\to \infty} f(x_n) \to M$ Then $\forall \epsilon>0, \exists N>0| n>N \implies |f(x_n)-M|\le \epsilon/2$

But we also have $|f(x_{n+1})-M|\le \epsilon/2$ using the same $N$.

So $|f(x_{n+1})-f(x_n)|\le |f(x_{n+1})-M|+|M-f(x_n)|\le \epsilon$

This establishes that $\lim_{n \to \infty} f(x_{n+1})-f(x_n)=0\implies f(x_{n+1})\to x_{n+1}$

By definition of a continous function $\forall \epsilon>0, \exists \delta$

Suppose $\forall n>0, |x_n-L|>\delta_0>0$

By another variation of the triangle inequality.

This implies $\forall n, |f(x_n)-L|>\delta_0$ contradicting that $f(x)$ converges.