3
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ 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$ $\endgroup$ – roman Dec 24 '18 at 17:14
  • 1
    $\begingroup$ The conditions $|x_{n+1}-x_n|<C\alpha^n$ and $0<\alpha <1$ imply that $C\geq 0.$ $\endgroup$ – DanielWainfleet Dec 24 '18 at 20:47
1
$\begingroup$

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$.

$\endgroup$
  • 1
    $\begingroup$ 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.$ $\endgroup$ – DanielWainfleet Dec 24 '18 at 21:18
  • $\begingroup$ I do, i will actually reaccept the answer since I find this one very useful. Thank you! $\endgroup$ – roman Dec 24 '18 at 21:42
  • $\begingroup$ 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. $\endgroup$ – DanielWainfleet Dec 24 '18 at 23:14
1
$\begingroup$

Seems fine.

We have $C \ge 0$.

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

$\endgroup$
1
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.