Proving whether or not a certain recursively defined sequence is a Cauchy sequence or not 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?
 A: 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.
A: 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$.
