$f:[0,1]\to[0,1]$ be a continuous function. Let $x_1\in[0,1]$ and define $x_{n+1}={\sum_{i=1}^n f(x_i)\over n}$.Prove, $\{x_n\}$ is convergent

Question

I have tried a little bit which as follows-
Since $f(x_n)\in[0,1]$, $\{f(x_n)\}$ has a convergent subsequence say $y_n=f(x_{r_n})\ \forall n\in\Bbb{N}$
Let, $\lim y_n=l\implies \lim \frac{y_1+y_2+\cdots+y_n}{n}=l\implies \lim \frac{f(x_{r_1})+f(x_{r_2})+\cdots+f(x_{r_n})}{n}=l$
But I am getting no idea to proceed and prove the convergence of $\{x_n\}$.
I have also tried to prove the sequence to be cauchy which goes-
$x_{m+1}-x_{n+1}={\sum_{i=1}^m f(x_i)\over m}-{\sum_{i=1}^n f(x_i)\over n}\le {\sum_{i=1}^m f(x_i)\over n}-{\sum_{i=1}^n f(x_i)\over n}$ (since $m\ge n)$
$\implies |x_{m+1}-x_{n+1}|\le \frac{|f(x_m)|+|f(x_{m-1})+\cdots+|f(x_{n+1})|}{n}\le\frac{m-n}{n}$ (since $f([0,1])\subseteq [0,1])$
Now, what will I get if I tend $m,n\to\infty$? But I need to do something more in the 2nd case since I have nowhere used the continuity of $f$.
Can anybody give an idea to prove it? Thanks for assistance in advance.

Answer 1

Note that $$\tag1x_{n+1}=\left(1-\frac1n\right)x_n+\frac1n f(x_n) $$ is a convex combination of $x_n$ and $f(x_n)$. In particular, $$ \tag2x_{n+1}-x_n=\frac{f(x_n)-x_n}n\to 0.$$

Clearly, $0\le \liminf x_n\le \limsup x_n\le1$. Assume $ \liminf x_n< \limsup x_n$. As the sequence must infinitely often walk from $\approx \liminf x_n$ up to $\approx \limsup x_n$ and according to $(2)$ must do so in arbitrarily small steps, we see that the set $$A:=\{\,x_n\mid x_{n+1}>x_n\,\}\cap (\liminf x_n,\limsup x_n)$$ is dense in $[\liminf x_n,\limsup x_n]$. Indeed, if $\liminf x_n<u<v<\limsup x_n$, then we find $n$ with $u<x_n<v$ as follows: From $(2)$, there exists $n_1$ with $|x_{n+1}-x_n|<v-u$ for all $n>n_1$. From the definition of $\liminf$, there exists $n_2>n_1$ with $x_{n_2}<u$. From the definition of $\limsup$, there exists $n_3>n_2$ with $x_{n_3}>v$. Let $n$ be maximal among $\{n_2, \ldots, n_3\}$ with $x_n< v$. Then (as certainly $n\ne n_3$) $x_{n+1}>v$ and hence $x_n>x_{n+1}-(v-u)\ge u$, so $u<x_n<v\le x_{n+1}$ and so $x_n\in A\cap (u,v)$.

Symmetrically, the set $$B:=\{\,x_n\mid x_{n+1}<x_n\,\}\cap (\liminf x_n,\limsup x_n)$$ is dense in $[\liminf x_n,\limsup x_n]$. Note that $f(x)>x$ for all $x\in A$ and $f(x)<x$ for all $x\in B$. Pick $a\in A$. Then $f(x)>x$ in an open neighbourhood $U$ of $a$. Then $B\cap U=\emptyset$, contradicting denseness. Therefore, we must have $\liminf x_n=\limsup x_n$, i.e., $\{x_n\}_{n\in\Bbb N}$ is convergent.

Answer 2

Given in problem, $f : [0, 1] \to [0, 1]$ is continuous. The sequence $\{x_{n}\}_{n \geqslant 1}$ is defined as following $$ x_{n + 1} = \frac{\sum_{k = 1}^{n} f(x_{k})}{n} $$ then we have a claim.

$\bullet$ $\textbf{Claim - 1:}~$ $x_{n}$ $\in$ $[0, 1]$ for any $n$ $\in$ $\mathbb{N}$.

$\bullet$ $\textit{Proof:}~$ The proof is a straightforward one with induction.

$\bullet$ $\textbf{Claim - 2:}~$ The sequence $\{ x_{n} \}_{n = 1}^{\infty}$ is a bounded sequence.

$\bullet$ $\textit{Proof:}~$ As the function $f$ $\in$ $\mathcal{C}[0, 1]$. Therefore we know that by Extremum Value Property of continuous functions, $f$ has a supremum and infimum. Let's denote it as $$ M := \sup_{x \in [0, 1]} \{ f(x)\} ~\text{ and }~ m := \inf_{x \in [0, 1]}\{ f(x) \}$$ Therefore we have that \begin{align*} & \frac{\sum_{k = 1}^{n} m }{n} \leqslant x_{n + 1} =~ \frac{\sum_{k = 1}^{n} f(x_{k})}{n} \leqslant~ \frac{\sum_{k = 1}^{n} M}{n} \quad[\text{as } m \leqslant x_{i} \leqslant M, \text{ for any } i \in \mathbb{N}]\\ \implies & \frac{mn}{n} \leqslant x_{n + 1} \leqslant \frac{Mn}{n}\\ \implies & m \leqslant x_{n + 1} \leqslant M \quad \text{for any } n \in \mathbb{N} \end{align*} Therefore $\{ x_{n} \}_{n \geqslant 1}$ is bounded.

$\bullet$ $\textbf{Claim - 3:}~$ The sequence $\{ (n - 1) x_{n} \}_{n \geqslant 1}$ is a monotonic sequence.

$\bullet$ $\textit{Proof:}~$ Observe that from the given,
$$ nx_{n + 1} = {\sum_{k = 1}^{n} f(x_{k})} $$ Therefore, we have that \begin{align*} nx_{n + 1} - (n - 1)x_{n} =&~ \sum_{i = 1}^{n} f(x_{i}) - \sum_{i = 1}^{n - 1}f(x_{i})\\ =&~ f(x_{n})\geqslant 0\\ \end{align*}
Thetefore we have that $~n x_{n + 1} \geqslant (n - 1)x_{n}~$ for any $n$ $\in$ $\mathbb{N}$. Therefore, $\{ (n - 1)x_{n} \}_{n \geqslant 1}$ is an increasing sequence.

$\bullet$ $\textbf{Claim - 4:}~$ The sequence $\{ x_{n} \}_{n \geqslant 1}$ is a monotonic sequence.

$\bullet$ $\textit{Proof:}~$ From the previous claim, we have that $\{ (n - 1)x_{n} \}_{n \geqslant 1}$ is an increasing sequence.

Therefore \begin{align*} &n x_{n + 1} - (n - 1)x_{n} \geqslant 0\\ \implies & n (x_{n + 1} - x_{n}) + x_{n} \geqslant 0\\ \implies & n (x_{n + 1} - x_{n}) \geqslant - x_{n}\\ \implies & n (x_{n} - x_{n + 1}) \leqslant x_{n}\\ \end{align*}
Now from this condition, we have to consider two cases.

$\bullet$$\bullet$ $\textbf{Case - I :}~$ When

\begin{align*} &0 \leqslant n ( x_{n} - x_{n + 1} ) \leqslant x_{n}\\ \implies & 0 \leqslant n (x_{n} - x_{n + 1})\\ \implies & x_{n} - x_{n + 1} \geqslant 0\\ \implies & x_{n} \geqslant x_{n + 1} \end{align*} Which implies that the sequence $\{ x_{n} \}_{n \geqslant 1}$ is a decresing sequence.

$\bullet$ $\bullet$ $\textbf{Case - II :}~$ When \begin{align*} &n (x_{n} - x_{n + 1}) \leqslant 0 \leqslant x_{n}\\ \implies & n (x_{n} - x_{n + 1}) \leqslant 0\\ \implies & (x_{n} - x_{n + 1}) \leqslant 0\\ \implies & x_{n} \leqslant x_{n + 1} \end{align*} Which implies that the sequence $\{ x_{n} \}_{n \geqslant 1}$ is increasing.

$\bullet$ $\bullet$ $\bullet$ From our previous claim of $\{ x_{n} \}_{n \geqslant 1}$ being bounded and as $\{ x_{n} \}_{n \geqslant 1}$ is either decreasing or increasing, therefore for respective cases we can use Monotone Convergence Theorem and hence imply that $\{ x_{n} \}_{n \geqslant 1}$ is convergent.

$\blacksquare~$ The proof may be faulty. If you find anything, please tell me :)

$\circ$ $\circ$ $\textbf{P.S:}~$ Can the problem be solved using $\textit{Stolz-Cesaro}$?

Answer 3

Note that the recurrence relation may be recast as

$$ x_{n+1} - x_n = \frac{f(x_n) - x_n}{n}. \tag{*} $$

Step 1. Let $\alpha = \liminf x_n$ and $\beta = \limsup x_n$. We first establish the following observation, which roughly shows that non-fixed points repel the sequence.

Lemma. Let $\ell \in [0, 1]$.

1. If $f(\ell) > \ell$ and there are infinitely many $n$'s for which $x_n \geq \ell$ holds, then $\ell \leq \alpha$.
2. If $f(\ell) < \ell$ and there are infinitely many $n$'s for which $x_n \leq \ell$ holds, then $\ell \geq \beta$.

Proof. We only prove the first part, since the proof of the second part will be similar.

Assume that $f(\ell) > \ell$ and there are infinitely many $n$'s for which $x_n \geq \ell$ holds. By the continuity of $x \mapsto f(x) - x$, there exists $\delta > 0$ such that $f(x) - x \geq 0$ on $[\ell-\delta, \ell+\delta]$.

Now choose $N$ so that $N > \delta^{-1}$ and $x_N \geq \ell$. We prove that $x_n \geq \ell$ for all $n \geq N$ by induction. Indeed, the base case is trivial by the choice of $N$. Next, assume that $n \geq N$ and $x_n \geq \ell$.

• If $x_n \leq \ell + \delta$, then by the choice of $\delta$, we have $x_{n+1} = x_n + \frac{f(x_n) - x_n}{n} \geq x_n \geq \ell$.

• If $x_n > \ell+\delta$, then $x_{n+1} \geq x_n - \left| \frac{f(x_n)-x_n}{n} \right| \geq (\ell + \delta) - \frac{1}{n} \geq \ell $.

Therefore the claim is true and the desired conclusion follows. $\square$

Step 2. Now we are in a position to prove the convergence of $(x_n)$.

Assume that $(x_n)$ does not converge. This implies that $\alpha < \beta$. Then any $\ell \in (\alpha, \beta)$ must be a fixed point of $f$, for otherwise $f(\ell) > \ell$ contradicts $\ell > \alpha$ and $f(\ell) < \ell$ contradicts $\ell < \beta$ by the lemma above. Moreover, since $|x_{n+1} - x_n| \to 0$, there exists $N$ for which $x_N \in (\alpha, \beta)$ holds. Then $x_N$ is a fixed point of $f$, and so, applying $\text{(*)}$ recursively shows that $x_{N+k} = x_N$ for all $k \geq 0$. Therefore $x_n$ is eventually constant and hence converges, contradicting the assumption.

Remark. The above lemma also shows that the limit of $(x_n)$ is a fixed point of $f$.