# Show uniqueness of solution to a function with infinite limit (and sequences).

I've got a question concerning some weird kind of Lipschitz constant function, but it's an introduction course in Mathematics, so Lipschitz continuity isn't part of the course (to my knowledge). Here's the question:

Introduction

Let $f:\mathbb{R}\rightarrow\mathbb{R}$ be a function and $a\in\mathbb{R}$. Define the sequence $(x_n)_{n\geq 0}$ by $x_0=a$ and for $n\geq 0, x_{n+1}=f(x_n)$.

Assume now that the function $f(x)$ has the following property: There is a constant $L\in(0,1)$ such that for all $x,y\in\mathbb{R}$ that following holds: $|f(x)-f(y)|\leq L|x-y|$.

Already Shown / Proven $$|x_{k+1}-x_k|\leq L^k|x_1-x_0|$$ For all $n>m\geq 0$ the following holds: $$|x_n-x_m|\leq\sum_{k=m}^{n-1}L^k|x_1-x_0|$$

The sequence $(x_n)_{n\geq 0}$ is convergent (by Cauchy).

Assignment

Show that $z$ defined by $z=\lim_{n\to\infty}x_n$ is the unique solution of the equation: $$x=f(x)$$

(So to prove: there is a solution, and there is at maximum one solution)

How far i've come

I don't really know what to do except write the following: $$z=\lim_{n\to\infty}x_n=\lim_{n\to\infty}f(x_{n-1})$$ Or: $$f(z)=f(\lim_{n\to\infty}x_n)=\lim_{n\to\infty}x_{n+1}??$$

I don't even know if this is correct. I just need a little push to get going.

This is known as the Banach fixed-point theorem. There is a solution to $f(x)=x$, namely $\lim_{n\to\infty}x_n$, since $$f(x) = f\left(\lim_{n\to\infty} x_n\right) = \lim_{n\to\infty}f(x_n)=\lim_{n\to\infty} x_{n+1} = x,$$ where continuity of $f$ justifies the interchange of limit. Now suppose $x'$ satisfies $f(x')=x'$. Then $$0 \leqslant |x'-x| = |f(x')-f(x)|\leqslant L|x'-x|.$$ Since $0<L<1$, this implies that $|x'-x|=0$, and hence $x'=x$, which means that the solution is unique.

There are a few things to do in this problem:

1. Show that there is a $z$ with $f(z) = z$
2. Show that this $z$ is unique
3. Show that the function converges
4. Show that the function must converge to such a $z$

1.

First we show that such a $z$ exists. Take $b = f(0)$. There are three cases. Either $b = 0$, $b < 0$ or $b > 0$. If $b = 0$, we are done. Otherwise, look at the function $g(x) = f(x) - x$ (I'm assuming $b$ is positive for simplicity, the exact same argument and $g$ works for $b$ negative). Note that for $z$ such that $f(z) = z$, we have $g(z) = 0$. We know that $g(0) = b$, and we have: $$g(b/(1-L)) = f(b/(1-L)) - b/(1-L)\\ = \big(f(b/(1-L)) - f(0)\big) + b - b/(1-L)\\ \leq |f(b/(1-L)) - f(0)| + b - b/(1-L) \\ \leq L|b/(1-L) - 0| + b - b/(1-L)\\ \leq L\frac{b}{1-L} + b - \frac{b}{1-L}\\ = \frac{bL + b(1-L) - b}{1-L} = 0$$ which means that either $g(b/(1-L)) = 0$, and we have our $z$, or we have $g(b/(1-L)) < 0$, which means that $g$ changes from positive to negative between $0$ and $b/(1-L)$, so by the intermediate value theorem. Either way, we've proven the existence of $z$.

2.

As for why there is a unique $z$ with $f(z)=z$, assume there are two such points $z_1,z_2$. Then $|f(z_1)-f(z_2)|=|z_1-z_2| > L|z_1 - z_2|$, which is not allowed.

3.

You've proven that the sequence is Cauchy, so it does converge to some value.

4.

Assume the limit is some number $y$ with $f(y)\neq y$, let's say $|f(y) - y| = \delta$. By definition of limit of a sequence, there is an $N \in \Bbb N$ such that for each $n> N$, we have $|y-x_n| < \delta/2$, say. This implies that $|y - x_{n+1}| = |y - f(x_n)| < \delta/2$. But we have $|f(y_n) - f(x_n)| < L\delta/2$. Therefore $$|y - f(x_n)| + |f(x_n) - y| < \frac\delta2 + L\frac\delta2 < \delta = |y - f(y)|$$ which violates the triangle inequality. Such a $y$ can therefore not be the limit of the sequence. That leaves the $z$ from above as the only available limit value, and since you know the limit exists, we are done.