Prove the convergence in recursive function

Question

Suppose the function $f:[0,1]\rightarrow [0,1]$ satisfying $|f(x)-f(y)|\leq \lambda|x-y|$, where $x,y \in [0,1]$ and $0<\lambda<1$. Randomly pick an initial point $x_0\in[0,1]$ and recursively defines a sequence $x_1=f(x_0), x_{n+1}=f(x_n)$, where $n=1,2,\dotsc$. Show that $\langle x_n\rangle^\infty_{n=1}$ converges and its limit point $x_*=\lim_{n\rightarrow\infty}{x_n}$ does not relate to the initial point $x_0$, where $x_*\in[0,1]$ and $f(x_*)=x_*$.

The hardest way in this problem is I couldn't think of the purpose of $\lambda$ here for the condition given, and I am stuck all the way. Any idea to prove it?

Answer 1

Suppose $x=f(x)$ and $y=f(y)$. Then $$ |f(x)-f(y)|<\lambda|x-y|=\lambda|f(x)-f(y)|<\lambda^2|x-y|<\dotsb $$ As $0<\lambda<1$, you get $|f(x)-f(y)|=0$, so in particular $x=y$.

Now, if $\langle x_n\rangle_{n\in\mathbb{N}}$ converges to $x_*$, it must be $$ f(x_*)=x_* $$ because $f$ is (uniformly) continuous and so $$ x_*=\lim_{n\to\infty}x_n=\lim_{n\to\infty}f(x_*)=f(x_*) $$ This proves that $x_*$ is independent on $x_0$.

Can you prove the sequence is convergent? Hint: it's Cauchy.

Answer 2

You may proceed as follows:

• From $|f(x)-f(y)|\leq \lambda|x-y|$ you can conclude that $f$ is continuous.
• $\Rightarrow f$ has a fixpoint $x^{\star} \in [0,1]$ as $f([0,1])\subset [0,1]$.

Now, for any starting value $x_0 \in [0,1]$ you get $$|x^{\star} - x_{n}| = |f(x^{\star}) - f(x_{n-1})|\leq \lambda |x^{\star} - x_{n-1}| \Rightarrow |x^{\star} - x_{n}| \leq \lambda^n|x^{\star} - x_0|\stackrel{n \to \infty}{\longrightarrow}0$$