Proving a sequence is bounded under given conditions

This question was asked in ISI BStat / BMath entrance exam:

Let $f :\mathbb{R}\to\mathbb{R}$ be a differentiable function such that its derivative $f'$ is a continuous function. Moreover, assume that for all $x ∈ \mathbb{R}$, $$0\le |f'(x)| \le \frac{1}{2}$$ Define a sequence of real numbers $\{ a_n \}_{n\in \mathbb{N}}$ by: $$a_1 =1, \\ a_{n+1}= f(a_n) \text{ for all } n\in\mathbb{N} \text{.}$$ Prove that the sequence $\{a_n\}$ is bounded.

My attempt:

If $a_{k+1}=a_{k}$ for some $k\in \mathbb{N}$, then $f(a_{k+1})=f(a_{k}) \Rightarrow a_{k+2}=a_{k+1}=a_{k}$. Likewise then for all $n\ge k$, we will have $a_{n}=a_k$. Thus, the sequence $\{a_n\}$ is constant eventually, hence, is bounded.

Now, we may assume $a_{k+1}\ne a_{k}$ for all $k\in \mathbb{N}$. For any $n \ge 3$, we claim that $|a_{n}-a_{n-1}|\le \frac{1}{2} |a_{n-1}-a_{n-2}|$. We prove it as follows: Note that $|a_n - a_{n-1}| = |f(a_{n-1}) - f(a_{n-2})|$ and by the Mean Value Theorem, we can find $c\in\mathbb{R}$ such that $|f(a_{n-1}) - f(a_{n-2})|=|f'(c) (a_{n-1}-a_{n-2})|= |f'(c) | |(a_{n-1}-a_{n-2})| \le \frac{1}{2} |(a_{n-1}-a_{n-2})|$. This proves our claim.

Now, for $n \ge 3$, we have $|a_n| = |a_n - a_1 + a_1| \le |a_n - a_1| + |a_1|$. We will try to obtain an upperbound for $|a_n - a_1|$.

$$ \begin{align} |a_n - a_1| &=|(a_n - a_{n-1}) + (a_{n-1} - a_{n-2}) + \ldots + (a_3 - a_2) + (a_2-a_1)| \\ &\le |a_n - a_{n-1}| + |a_{n-1} - a_{n-2}| + \ldots + |a_3 - a_2| + |a_2-a_1| \\ &\le \frac{1}{2^{n-2}} |a_2-a_1| + \frac{1}{2^{n-1}} |a_2-a_1| + \ldots + \frac{1}{2} |a_2-a_1| + |a_2-a_1| \\ & = \left( 1+ \frac{1}{2} + \ldots + \frac{1}{2^{n-2}} \right) |a_2-a_1| < 2|a_2 - a_1| \end{align} $$ Thus,we showed that $|a_n| < 2 |a_2 - a_1| + |a_1|$ for all $n\ge 3$. Thus, $\{ a_n \}$ is bounded.

Though, it looks to me that my proof is correct but I have failed to use the fact that $f'$ is a continuous function. Are there any flaws in my proof? Alternative proofs are welcome.

Solution 1:

If $|f'(x)|$ is bounded by $L$ then $f$ is Lipschitz with constant $L$. Here we have $L=\frac{1}{2}$ and so $f$ is a contraction mapping. The Banach fixed point theorem says that $x_n = f(x_{n-1})$ has a unique fixed point and the sequence $x_n$ generated this way is convergent and thus bounded.