Proving whether or not a certain recursively defined sequence is a Cauchy sequence or not

Question

Question:

Let $\{x_{n}\}$ be a recursively defined sequence defined as: $$x_{1} = \frac{1}{2}$$ $$x_{n+1} = \frac{1-x_{n}}{4}$$

I want to show first that $|x_{n+1}-x_{n}| \le \frac{1}{4}|x_{n}-x_{n-1}|$. Using this, I have to prove that the sequence is Cauchy and then find its limit. Here is what I have done:

Part 1:

$$|x_{n+1}-x_{n}| = \left|\frac{1-x_{n}}{4} - \frac{1-x_{n-1}}{4}\right| \\ =\left|\frac{-x_{n}}{4} + \frac{x_{n-1}}{4}\right| = \frac{1}{4}|-x_{n}+x_{n+1}|$$

But, I do not know how to go from this equality to the inequality that the question has. How may I manipulate the equation so that the $=$ changes to a $\le$?

Part 2:

Now as for the second subpart where I have to show that the sequence is Cauchy, I am not sure where to start, so I started with the definition of Cauchy sequence, which is as follows:

A sequence $\{a_{n}\}$ is called a Cauchy sequence if $\forall \epsilon>0 \exists N \in \mathbb{N}$ s.t. if $m,n \ge N$, then $$|a_{m}-a_{n}| < \epsilon$$ But the problem I face is that if I try to use this definition and try to apply it here, I am getting that: $$x_{m}-x_{n} = \left|\frac{-x_{m-1}}{4}+\frac{x_{n-1}}{4}\right|$$ But after this, how can I use my previous result to prove that this is always bounded by $\epsilon$?

Could someone help me?

Answer 1

You have found $|x_{n+1}-x_n| =\frac14|-x_n+x_{n-1}| = \frac14|x_n-x_{n-1}|$, which satisfies the inequality. If you insist, write $|x_{n+1}-x_n| \le |x_{n+1}-x_n| = \frac14|x_n-x_{n-1}|$ and now you have the inequality.

Using this we see that for any $n$:

$$|x_{n+1}-x_n|\le\frac14|x_n-x_{n-1}| \le \frac1{4^2}|x_{n-1}-x_{n-2}| \le\cdots\le\frac1{4^{n-1}}|x_2-x_1|=\frac1{2^{2n-2}}\cdot\frac38 = \frac3{2^{2n+1}}$$

The "$\cdots$" can be made rigorous via induction on $n$.

Now suppose $m > n$. Then

\begin{align}|x_m-x_n| &\le |x_m-x_{m-1}| + |x_{m-1}-x_{m-2}| + \cdots + |x_{n+1}-x_n|\\ &=\sum_{k=n}^{m-1}|x_{k+1}-x_k|\\ &\le\sum_{k=n}^{m-1}\frac{3}{2^{2k+1}}\\ &<\sum_{k=n}^{\infty}\frac{3}{2^{2k+1}}\\ &=\frac {3}{2^{2n+1}}\div\left(1-\frac14\right)\\ &=\frac1{2^{2n-1}}\end{align}

Using this upper bound, it should be easy to find the $N \in \mathbb N$ for any arbitrary $\epsilon >0$.

Answer 2

Let $f : [0,1] \rightarrow [0,1]$ be the function defined for all $x \in [0,1]$ by $$f(x)=\frac{1-x}{4}$$

First, $f$ is well-defined because it is decreasing over $[0,1]$, and $f(0), f(1) \in [0,1]$. Because $x_1 = 1/2 \in [0,1]$, you deduce by an easy induction that the sequence $x_{n+1} = f(x_{n-1})$ is well-defined and takes all its values in $[0,1]$.

For any integer $n \geq 1$, the MVT applied to the function $f$ between $x_n$ and $x_{n-1}$ gives $$|x_{n+1}-x_n|=|f(x_n)-f(x_{n-1})| = \frac{1}{4}|x_n -x_{n-1}| \quad \quad (*)$$

(because $f' \equiv -1/4$ over $[0,1]$). This is the first part.

Now, for every integers $q>p$, you can see by an easy induction (using the equality $(*)$), that
$$|x_q-x_p|= \frac{1}{4^{p-1}}|x_{q+1-p}-x_1| \leq \frac{1}{4^{p-1}}$$

This proves that the sequence is Cauchy, and you are done.