# Need help with the proof that there exists an $x_0$ such that $f(x_0)=x_0$ for the function defined as $|f(x)-f(y)| \leq L|x-y|$ with $0<L<1$

I need to show that there exists a unique $x_0\in \mathbb R$ such that $f(x_0)=x_0$ for the function defined as $|f(x)-f(y)| \leq L|x-y|$ such that with $0<L<1$ and $f: \mathbb R \to \mathbb R$.

Here is what I attempted to do: I will prove that $x_0$ must be unique by contradiction. Assume that there exists two distinct values, $x_1$ and $x_2$ such that $f(x_1)=x_1$ and $f(x_2)=x_2$ and $x_1 \neq x_2$.

Observe that \begin{align}|f(x_1)-f(x_2)|\leq L|x_1-x_2| & \iff |x_1-x_2| \leq L|x_1-x_2| \\ &\iff \frac{|x_1-x_2|}{|x_1-x_2|}\leq L \\& \iff 1 \leq L \end{align} which contradicts the definition of $L$ which says that $0<L<1$, and thus there must only exist one value $x_0$ such that $f(x_0)=x_0$.

The only thing is, this seems too easy and can't possibly be the complete solution. Should I have started by proving that $f(x_0)=x_0$ somehow or that the function is continuous?

Rearranging the given inequality gives \begin{align}\frac{|f(x)-f(y)|}{|x-y|} & \leq L \iff \\ \left|\frac{f(x)-f(y)}{x-y}\right| & \leq L\end{align} which makes me think of the mean value theorem, and if I take the limit as $x \rightarrow x_0$ of both sides this reminds me of the definition of a function being differentiable if the limit exists and is finite.

Can someone tell me if I am approaching the problem correctly? Any hints would be greatly appreciated.

(Also I looked at a similar question where they also mentioned continuity, so now I feel that that needs to be addressed in my solution to the problem.)

-
This seems to be pretty messy: first, your function is not defined as what you say, but fulfills that condition; second, the function must be continuous non-constant otherwise the claim is false; third, assuming the above, you still haven't proved that there exists such a fixed point for that point: you only proved that there exists at most one such fixed point... – DonAntonio Apr 22 '13 at 16:19
Was the downvote because, as DonAntonio mentioned, my attempt at a solution was messy? – user66807 Apr 22 '13 at 22:22
I don't think so, @user66807. Perhaps it is one of our serial downvoters, which downvote just because. Don't worry about that. – DonAntonio Apr 22 '13 at 23:17

Hint: You've shown that if a fixed point exists, it is unique. To prove existence, think of compositions and the fact that $L^n\to0$ as $n\to\infty$.

-
okay I understand that when $n \rightarrow \infty$, $L^n \rightarrow 0$, but I am not sure why we are using this fact. Here is what I came up with \begin{align}\frac{|f(x)-f(y)|}{|x-y|} & \leq L \iff \\ \left|\frac{f(x)-f(y)}{x-y}\right| & \leq L \iff \\ \left|\frac{f(x)-f(y)}{x-y}\right|^n & \leq L^n \end{align} Taking limit of both sides gives $\lim_{n \to \infty} \left|\frac{f(x)-f(y)}{x-y}\right|^n \leq 0$ Am I on the right track? (I just found something on compositions in my textbook, I'll read it and see if I understand your hint better.) – user66807 Apr 22 '13 at 17:19
@user66807: Instead, think about repeated compositions of a single point. That is, if $f^{(n)}(x)=f\circ\cdots\circ f(x)=x_n$, then the fact that $L^n\to0$ tells you this is a Cauchy sequence. In other words, for every $\varepsilon>0$, there exists $N>0$ such that for $m,n>N$, $|x_m-x_n||<\varepsilon$. Completeness of the real line tells you that a Cauchy sequence must converge, i.e., there is a point $x_0$ with $f(x_0)=x_0$. – Clayton Apr 22 '13 at 17:33
It makes more sense now, but I'm still confused. I don't think I ever got the hang (or understanding) of how to prove a sequence is Cauchy.All I know is that if I prove a sequence is Cauchy then I have proved that it converges. This is how I was shown to show the Cauchy property. With $x_n=f^{(n)}(x)=f\circ\cdots\circ f(x)$ $n$ times, then $x_m=f^{(m)}(x)=f\circ\cdots\circ f(x)$ $m$ times. Assume $m\geq n$, then $|x_m-x_n||<\epsilon \iff |f^{(m-n)}(x)|<\epsilon$. Is this what you are doing as well? If so, how does $L^n\to0$ tell me this is Cauchy? Thanks a lot for your help, too. – user66807 Apr 22 '13 at 17:58
Oh I think I just got it. Since $|x_m-x_n|=|f^{(m-n)}(x)|< L^n$ and since $L^n \to 0$ as $n \to \infty$ we have that $|f^{(m-n)}(x)|$ is bounded above by something that goes to $0$ and since $\epsilon > 0$ we have that $x_n$ is a Cauchy sequence. I understand that the sequence converges, but how does this tell us that $f(x_0)=x_0$? – user66807 Apr 23 '13 at 3:45
@user66807: If it didn't, then we could keep iterating and that wouldn't be the limit point. – Clayton Apr 23 '13 at 12:25

Hints about the existence of a fixed point with $\,f\,$ continuous:

1) Let $\,x\in\Bbb R\,$ be any point, and define $\,x_1=f(x)\;,\;x_n:=f(x_{n-1})\;,\;2\le n\in\Bbb N\,$

2) Show $\,\{x_n\}\,$ is a Cauchy sequence

3) Show that $\,x_0:=\lim\limits_{n\to\infty}x_n\,$ fulfills $\,f(x_0)=x_0\,$

-
Isn't the continuity a consequence of the function being Lipschitz? – Clayton Apr 22 '13 at 17:38
Indeed so, yet I didn't see in the OP mentioning this (in fact, he even asks whether he has to prove continuity). That's why I remark it. – DonAntonio Apr 22 '13 at 18:10
@Clayton That is because I don't know what Lipschitz is. – user66807 Apr 22 '13 at 18:42