# Proof verification. $\{x_n\}$ is a sequence such that $|x_{n+1} - x_n| \le C\alpha^n$ for $\alpha\in (0, 1), n\in\Bbb N$. Prove $x_n$ converges.

Let $$\{x_n\}, n\in \Bbb N$$ denote a sequence such that: $$\begin{cases} |x_{n+1} - x_n| \le C\alpha^n \\ 0 < \alpha < 1 \end{cases}$$ Prove $$\{x_n\}$$ converges.

Given the fact $$|x_{n+1} - x_n| \le C\alpha^n$$ consider the following inequalities: $$|x_{n+1} - x_n| \le C\alpha^n \\ |x_{n+2} - x_{n+1}| \le C\alpha^{n+1} \\ |x_{n+3} - x_{n+2}| \le C\alpha^{n+2} \\ \dots \\ |x_{n+p+1} - x_{n+p}| \le C\alpha^{n+p} \\$$

Consider the sum of the inequalities: $$|x_{n+1} - x_{n}| + |x_{n+2} - x_{n+1}| + |x_{n+3} - x_{n+2}| + \cdots + |x_{n+p+1} - x_{n+p}| \\ \le \sum_{k=0}^p C\alpha^{n+k} = C \sum_{k=0}^p \alpha^{n+k} \tag1$$

By geometric sum: $$C \sum_{k=0}^p \alpha^{n+k} = C \cdot \frac{\alpha^n(1-\alpha^{p + 1})}{1-\alpha} \le C \cdot \frac{\alpha^n}{1-\alpha}$$

Lets fix some $$\epsilon > 0$$, and $$N\in \Bbb N$$ such that: $$C\cdot \frac{\alpha^{N}}{1-\alpha} < \epsilon$$

Rewrite $$\alpha$$ as: $$\alpha = \frac{1}{1+r},\ r \in \Bbb R_{>0}$$

Thus: $$C\cdot \frac{1}{(1-\alpha)(1+r)^N} < \epsilon \\ (1+r)^N > {C\over (1-\alpha)\epsilon} \\ N > \log_{1+r} {C\over (1-\alpha)\epsilon}$$

Returning to $$(1)$$ we have by triangular inequality: $$|x_{n}- x_{n+1} + x_{n+1} - x_{n+2} + \cdots + x_{n+p} - x_{n+p+1}| \\ \le |x_{n+1} - x_{n}| + |x_{n+2} - x_{n+1}| + \cdots + |x_{n+p+1} - x_{n+p}|$$

Since the values are telescoping we obtain: $$|x_{n} - x_{n+p+1}| < C \cdot \frac{\alpha^n}{1-\alpha} < \epsilon$$

Now if we choose: $$n > N > \log_{1+r} {C\over (1-\alpha)\epsilon}$$ we obtain a regular definition of the Cauchy criteria, which means $$\{x_n\}$$ is a convergent sequence.

Could you please verify the reasoning above? Thank you!

• The constraints on $C$ are not given in the source of the problem statement, but the only reasonable way seems to be: restrict $C > 0$ – roman Dec 24 '18 at 17:14
• The conditions $|x_{n+1}-x_n|<C\alpha^n$ and $0<\alpha <1$ imply that $C\geq 0.$ – DanielWainfleet Dec 24 '18 at 20:47

You have the right idea but it could be briefer: Let $$A(n)=\sup_{m\in \Bbb N}|x_n-x_{n+m}|.$$ The Cauchy Criterion for convergence of $$(x_n)_{n\in \Bbb N}$$ is $$\lim_{n\to \infty}A(n)=0.$$

Since $$0<\alpha<1$$ we have $$\sup_{m\in \Bbb N}(1-\alpha^m)=1,$$ so $$A(n)=\sup_{m\in \Bbb N}|x_n-x_{n+m}|\leq$$ $$\leq \sup_{m\in \Bbb N}C\alpha^n\cdot\frac {1-\alpha^m}{1-\alpha}=$$ $$=C\alpha^n\cdot \frac {1}{1-\alpha}.$$ This last expression goes to $$0$$ as $$n\to \infty$$ because $$0<\alpha <1$$.

• I am assuming that you already know that $a^n\to 0$ as $n\to \infty$ if $0<a<1....$ Let $a=1/(1+b)$ with $b>0$. By the Binomial theorem, if $n\in \Bbb N$ then $(1+b)^n\geq 1+nb,$ so $1/a^n=b^n\to \infty$ as $n\to \infty.$ – DanielWainfleet Dec 24 '18 at 21:18
• I do, i will actually reaccept the answer since I find this one very useful. Thank you! – roman Dec 24 '18 at 21:42
• Here's one I once needed as an intermediate result : $x_n\in \Bbb R$ and $|x_n-x_m|\leq 1/n+1/m$ for all $n,m\in \Bbb N.$ Then $(x_n)_n$ converges. – DanielWainfleet Dec 24 '18 at 23:14

Seems fine.

We have $$C \ge 0$$.

In the event that $$C=0$$, we have a constant sequence and hence it converges.

This is a comment rather than an answer.

You don't have to use logs.

By Bernoulli's inequality, $$(1+r)^N \ge 1+rN \gt rN$$ so that $$C \frac{1}{(1-\alpha)(1+r)^N} \lt C\frac{1}{(1-\alpha)rN}$$.

Therefore, if $$\epsilon \gt C \frac{1}{(1-\alpha)rN}$$, or $$N > \frac{C}{(1-\alpha)r\epsilon}$$, then $$C \frac{1}{(1-\alpha)(1+r)^N} < \epsilon$$.

Of course this isn't as good as the equation using logs, but it is completely elementary.

• Indeed, thanks for pointing out – roman Dec 24 '18 at 20:01