# Please help prove that $(x_n)$ is a Cauchy sequence if $|x_{n+1} - x_n| \leq Cr^n$

Past final exam question for an intro to Real Analysis course:

Let $C > 0$, $0<r<1$ and suppose that $\forall n\in \mathbb N, |x_{n+1} - x_n| \leq Cr^n$. Please help me prove that $(x_n)$ is a Cauchy sequence. (We can assume the $\lim\limits_{n\to\infty} r^n=0,$ for $0<r<1$)

So, I know that a Cauchy series must satisfy $|x_{n}-x_m| < \epsilon$ for any $\epsilon>0, \in \mathbb R$ and for all $n,m \gt H(\epsilon) \in \mathbb N$ Note that there can't be any conditions on n and m (I saw somewhere else someone required $m>n$ which you can only do if you're proving its not at Cauchy sequence, right?)

Another way of doing this is showing that it is contractive (and thus a Cauchy series) if there is a constant $a$ such that $|x_{n+1}-x_n| \leq a|x_n-x_{n-1}|$

Clearly I'm supposed to make use of $\lim\limits_{n\to\infty} r^n=0,$ for $0<r<1$... But I don't even know how where to start with this. As I am bumbling through this problem, a more thorough answer would be much appreciated. Thanks!

• Well you solved it. – user67773 May 1 '13 at 9:45
• @Uma kant, I haven't really done much actually. I have simply stated some theorems about Cauchy and contractive sequences, which doesn't get me very far. – Christian May 1 '13 at 9:47
• @Umakant No, not yet completely. Neither can we find $a$ with $|x_{n+1}-x_n|\le a|x_n-x_{n-1}|$ for almost all $n$ (we might have $x_n=x_{n-1}$ infinitely often); nor is $\lim_{n\to\infty} Cr^n=0$ sufficient (note that we'd also have $\lim_{n\to\infty}\frac Cn=0$, but $x_n=\ln n$ is not Cauchy). – Hagen von Eitzen May 1 '13 at 9:50
• You can assume $n > m$ without loss of generality since $|x_{n} - x_{m}| = |x_{m} - x_{n}|$. – Vincent Pfenninger May 1 '13 at 9:51

## 3 Answers

Let $\epsilon>0$ be given. Then we can find $N$ such that $r^N\frac C{\color{red}{1-r}}<\frac\epsilon2$ because $r^n\color{red}\to0$ as $n\to \infty$. Then for any $n>N$ we have \begin{align} |x_n-x_N|&\le|x_{N+1}-x_N|+\ldots+ |x_n-x_{n-1}|\\&\le Cr^N+Cr^{N+1}+\ldots +Cr^{n-1} \\&=Cr^N\cdot(1+r+\ldots + r^{n-N-1}) \\&\color{red}<Cr^N\sum_{k=0}^\infty r^k \color{red}= Cr^N\cdot\frac1{1-r}<\frac\epsilon2,\end{align} hence for $n,m>N$ $$|x_n-x_m|\le|x_n-x_N|+|x_m-x_N|<\frac\epsilon2+\frac\epsilon2=\epsilon.$$

Remark: I've marked all places in red where we made use of $0<r<1$.

• +1. a little modification of your proof, it is as good as yours: $|x_n-x_N|\leq Cr^N+Cr^{N+1}+\ldots +Cr^{n-1}=C(r^N+r^{N+1}+\ldots+r^{n-1})=C\frac{r^N(1-r^{n-N})}{1-r}\leq C\frac{r^N}{1-r}<\epsilon/2$. – Eric Jan 31 '17 at 6:50
• Also, the "final" step of the proof can also be shown by: for $m,n>N$, without lost of generality, let $m$ be the bigger number(i.e. $m>n$), then $|x_m-x_n|\leq |x_n-x_{n+1}|+\ldots+|x_{m-1}+x_m|\leq|x_N-x_{N+1}|+|x_{N+1}-x_{N+2}|+\ldots+(|x_n-x_{n+1}|+\ldots+|x_{m-1}+x_m|)=|x_m-x_N|<\epsilon/2$. – Eric Jan 31 '17 at 7:03
• (in this way, the $N$ need not choose to satisfy $C\frac{r^N}{1-r}<\epsilon/2$. Only need to be less than $\epsilon$) – Eric Jan 31 '17 at 7:04

Hint: $|x_n-x_m|\le |x_n- x_{n-1}|+|x_{n-1}-x_{n-2}|+\dots+|x_{m+1}-x_{m}|$.

We don't need to assume $r^n\xrightarrow{n\to\infty}0$. Since $|r|<1$, $$\sum_{n=1}^\infty r^n=\frac r{1-r}$$ and hence $r^n\xrightarrow{n\to\infty}0$.

The desired claim can easily be generalized: Let $(E,d)$ be a metric space, $(x_n)_{n\in\mathbb N}\subseteq E$ and $(\varepsilon_n)_{n\in\mathbb N}\subseteq\mathbb R$ be summable with $$d(x_n,x_{n+1})<\varepsilon_n\;\;\;\text{for all }m,n\ge N\tag1$$ for some $N\in\mathbb N$.

We show that $(x_n)_{n\in\mathbb N}$ is Cauchy: Let $\varepsilon>0$. Since $(\varepsilon_n)_{n\in\mathbb N}$ is summable, $\left(\sum_{i=1}^n\varepsilon_i\right)_{n\in\mathbb N}$ is Cauchy and hence $$\sum_{i=m+1}^{n}\varepsilon_i=\left|\sum_{i=1}^m\varepsilon_i-\sum_{i=1}^n\varepsilon_i\right|<\varepsilon\;\;\;\text{for all }n\ge m\ge N_1\tag2$$ and hence $$d(x_m,x_n)=\sum_{i=m}^{n-1}d(x_i,x_{i+1})<\sum_{i=m}^{n-1}\varepsilon_i<\varepsilon\;\;\;\text{for all }n\ge m>\max(N,N_1).\tag3$$