Showing a recursively defined sequence is convergent using Banach fixed-point theorem

Question

I recently stumbled across an interesting question, in which we need to show a recursively defined sequence $(x_n)_{n\in\mathbb{N}}$ in $\mathbb{R}$ defined as follows

$$ x_0 = 4 , \quad x_{n+1}=\ln\left(3-\frac{x_n}{2}\right) \quad \text{for} \ \ \ n \ge 1 $$

is convergent using the Banach Fixed-Point Theorem.

I am familiar with how to show a function is convergent using the Banach Fixed-Point Theorem given, but I haven't necessarily seen it be used on a recursively defined sequence. I'd assume you could use generating functions, but is there an easier way?

I would be thankful for any help.

Answer 1

Here are some possible steps.

• Prove that $T : [0, 4] \to [0, 4]$, with $T(x) = \ln \left( 3 - \tfrac x 2 \right)$, is a well-defined function. (You'll need to prove that if $x \in [0, 4]$, then $T(x) \in [0, 4]$ too.)
• Prove that $T$ is a contraction, with $|T(x_1) - T(x_2)| \leq \tfrac 1 2 |x_1 - x_2|$ for all $x_1, x_2 \in [0, 4]$. (I suggest you do this by showing that $|T'(x)| \leq \frac 1 2$ for all $x \in [0, 4]$.)
• Use the fact that $T$ is a contraction to deduce that the sequence defined by $x_0 = 4$ and $x_{n+1} = T(x_n)$ for $n \geq 1$ is a Cauchy sequence.
• Explain why $[0, 4]$ is a complete metric space.
• Conclude that the sequence $x_n$, being Cauchy, is convergent.

Bullet points 3 and 5 use ideas from the proof of the Banach fixed point theorem. So you can view this solution strategy as an "application" of the Banach fixed point theorem.

Answer 2

Usually, the fixed point theorem is used on recursive function by finding $f$ such that $x_{n+1} = f(x_n)$.

From there, all you need to do is make sure all the necessary conditions are satisfied (in this case, contraction), and you can apply the theorem to show it's convergent.

Answer 3

The Banach Fixed-Point Theorem shows that if a map $T\colon X\to X$ is a contraction then it has a unique fixed point, provided that $X$ is a non-empty complete metric space. For $T$ to be a contraction there must be a constant $K$ with $d(T(x),T(y))\leq K.d(x,y)$ for all $x,y \in X$.

The theorem is proved by picking an arbitrary point $x_0 \in X$, which you think of as an initial "guess" at where the fixed point is. You then consider the sequence $(x_n)_{n \geq 0}$ defined recursively by $x_{n+1} = T(x_n)$. Using the contraction condition you can show this is a Cauchy sequence and so if $X$ is complete it has a limit, say $y\in X$. The limit must satisfy $$ T(y)=T(\lim_{n \to \infty} x_n) = \lim_{n\to \infty} T(x_n) =\lim_{n\to \infty} x_{n+1} =y, $$ since $T$ is continuous (in fact Lipschitz continuous). The fixed point is unique because if $z_1,z_2$ are fixed points, then $d(z_1,z_2) = d(T(z_1),T(z_2))\leq K.d(z_1,z_2)$ and hence since the distance function is non-negative and $K\in (0,1)$ we must have $d(z_1,z_2)=0$ and so $z_1 =z_2$. Another way of phrasing the uniqueness part is to note that, if $z_0$ is a fixed point, then $$ d(z_0,x_{n+1}) = d(z_0,T(x_n))= d(T(z_0),T(x_n))\leq Kd.(z_0,x_n), $$ so by induction $d(z_0,x_n) \leq K^nd(z_0,x_0) \to 0$ as $n\to \infty$, hence $y=z_0$.

Hopefully this helps in seeing how the theorem is relevant to the sequence you are given!