Fixed point in a metric space with distance at most 1 The question is:
Suppose that $X$ is a complete metric space such that the distance function is at most 1, and $f:X\rightarrow X$ is such that $d(f(x),f(y))\le d(x,y)−1/2(d(f(x),f(y)))^2$.
Prove that $f$ has a unique fixed point $x_0\in X$ and $\lim_{n\to\infty} f^{n}(x)=x_0$ for any $x\in X$.
I assume I must use that Cauchy sequences converge in $X$ but when I set up the inequality, I get:
$d(f^m(x),f^n(x))=\sum_{k=0}^{m-n-1} d(f^{n+k+1},f^{n+k})\le (m-n)d(f(x),x)-(1/2)(\sum_{k=0}^{m-n-1} d(f^{n+k+1},f^{n+k})^2)$
attempting to mirror the proof of the contraction principle, but we have no guarantee that the right hand side goes to zero.
 A: There must be a quicker proof than this, but the first argument I came up with  is the following (this is just a sketch, I'm leaving the details to you). 
Step 1: Solving the inequality $d(fx, fy) \leq d(x,y) - \frac{1}{2}d(fx, fy)^2$ for $d(fx, fy)$ gives the inequality $$d(fx, fy)\leq -1 + \sqrt{1 + 2d(x,y)} = \left(\frac{-1 + \sqrt{1 + 2d(x,y)}}{d(x,y)}\right)d(x,y).$$
Step 2: Note that you have the inequality $$\frac{-1 + \sqrt{1 + 2d(x,y)}}{d(x,y)} < 1$$ when $d(x,y)\neq 0$. From this you can conclude two things:


*

*$d(fx, fy) \leq d(x,y)$ for all $x,y$, and 

*For each $\delta>0$ there is a $\theta$ with $0<\theta<1$ such that if $d(x,y)\geq \delta$, then $d(fx, fy) \leq \theta d(x,y)$.


Step 3: Fix a point $x\in X$, and consider the sets $Y_n = \{f^nx, f^{n+1}x, \ldots\}$ for $n\geq 0$. Note $Y_{n+1}\subseteq Y_n$, so in particular the sequence $\Delta_n = \mathrm{diam}(Y_n)$ is monotonically decreasing. Let $\delta = \lim \Delta_n$. I claim that $\delta = 0$. 
Why is this? Suppose for contradiction that $\delta>0$. By step 2, we know that there is a $\theta\in (0,1)$ such that if $d(x,y)\geq \theta$, then $d(fx, fy)\leq \theta d(x,y)$. Let $\epsilon>0$ be such that $$\epsilon < \delta\left(\frac{1-\theta}{\theta}\right).$$ Since $\Delta_n$ monotonically decreases to $\delta$, there is an $N$ such that $\delta\leq\Delta_n < \delta + \epsilon$ for all $n\geq N$. Applying this to $n = N+1$ yields that there exist integers $i,j\geq N+1$ such that $$\delta \leq d(f^ix, f^jx)< \delta + \epsilon.$$ Since by step 2 we know that $f$ does not increase distances, $d(f^ix, f^jx)\leq d(f^{i-1}x, f^{j-1}x)$. On the other hand, $\Delta_N< \delta + \epsilon$, so we have $\delta \leq d(f^{i-1}x, f^{j-1}x) < \delta + \epsilon$. But here's where we reach a contradiction, because now $$\delta \leq d(f^ix, f^jx) \leq \theta d(f^{i-1}x, f^{j-1}x) <\theta(\delta + \epsilon),$$ which implies $\epsilon > \delta(1-\theta)/\theta$. This proves that in fact $\delta = 0$.
Step 4: The closures $\overline{Y}_n$ have the same diameters $\Delta_n$ as the sets $Y_n$, so $\overline{Y}_n$ is a nested sequence of closed sets with diameters tending to $0$. By completeness, it follows that $\bigcap\overline{Y}_n = \{x_*\}$ for some point $x_*\in X$. It is now easy to check (and you should!) that $f^nx\to x_*$ as $n\to \infty$, and that $x_*$ is a fixed point of $f$. Thus we have shown:

For every $x\in X$, there is a fixed point $x_*\in X$ such that $f^nx\to x_*$ as $n\to \infty$.

Step 5: To complete the proof, it now suffices to note that $f$ can have at most one fixed point. Indeed, if $x_0$ and $x_1$ were two distinct fixed points, then since $d(x_0, x_1)\neq 0$, we have $d(fx_0, fx_1)<d(x_0, x_1)$, which is absurd, since $fx_0 = x_0$ and $fx_1 = x_1$.
