Cauchy sequence that satisfies $\|x_{k+2}-x_{k+1}\|\le\theta\|x_{k+1}-x_k\|$

Question

Suppose the sequence $\{x_k\}_{k=1}^\infty\subset\mathbb{R}^n$ satisfies $\|x_{k+2}-x_{k+1}\|\le\theta\|x_{k+1}-x_k\|$ for all $k\ge1$, with $0<\theta<1$. Show that $\{x_k\}$ is a Cauchy sequence and hence converges.

---

So I did some rearranging to try and get something that worked and got this:

For $m,n>1$ such that $m<n$ $$\|x_n-x_m\|=\|x_n+\left(\sum_{i=m+1}^{n-1}(x_i-x_i)\right)-x_m\|$$ $$\le \sum_{i=m+1}^n\|x_i-x_{i-1}\|\text{ (triangle inequality)}$$ $$\le\left(\sum_{i=0}^{n-m}\theta^i\right)\|x_{m+1}-x_m\|$$

Is it sufficient to choose $N$ for any $\epsilon$ such that $\|x_{N+1}-x_N\|<\epsilon$ and since $\left(\sum_{i=0}^{n-m}\theta^i\right)<1$ I can use the above derivation?

Answer 1

A hint: Prove by induction that $$|x_{k+1}-x_k|\leq \theta^k|x_1-x_0|\qquad(k\geq0)\ ,$$ then use (as you did) the triangle inequality and the infinite series $\sum_{k\geq n}\theta^k$ to estimate $|x_{n+p}-x_n|$. Don't be afraid of ${|x_1-x_0|\over 1-\theta}$.

Answer 2

By induction it follows that $$\|x_{k+1}-x_k\| \leq \theta^k\|x_1-x_0\|$$ so, if $n>m$, we have: $$\begin{align} \|x_n-x_m\| &\leq \| x_n - x_{n-1}\| + \ldots + \| x_{m+1} - x_m\|\\ &\leq (\theta ^{n-1}+\ldots+\theta^m)\|x_1-x_0\|\\ &\leq\left(\sum_{k=0}^{n-1}\theta^k - \sum_{k=0}^{m-1}\theta^k \right)\|x_1-x_0\|\\ &\leq\left(\frac{1-\theta^n}{1-\theta}-\frac{1-\theta^m}{1-\theta} \right)\|x_1-x_0\|\\ &\leq (\theta^m - \theta^n)\frac{\|x_1-x_0\|}{1-\theta} \end{align} $$ and similarly in case of $n < m$: $$\|x_n-x_m\| \leq (\theta^n - \theta^m)\frac{\|x_1-x_0\|}{1-\theta}$$ Thus, in general we have: $$\|x_n-x_m\| \leq \|\theta^n - \theta^m\|\frac{\|x_1-x_0\|}{1-\theta}$$

Now, since $0<\theta<1$, sequence $(\theta^n)_{n\in\mathbb N}$ converges to $0$, hence, it is Cauchy sequence. If you use it on previous inequality, the desired conclusion will easily follow.