Show that a recursive sequence $(x_n)$ is Cauchy

Question

The given sequence is defined as $x_1 = 0$, $x_2 = 1$ and $x_{n+2} = \frac{1}{3}x_{n+1} + \frac{2}{3}x_n$ for $n \geq 1$. I seek to show that it is Cauchy.

So how I planned on showing this was to first find a recurrence relation between the distance of $x_n$ and $x_{n+1}$. That is $|x_n - x_{n+1}| = \lambda$ for some $\lambda$. Then show that knowing this, for $m \geq n$, by grouping terms, we can show that it is bounded, convergent and hence Cauchy.

Approach jumps out to me because I've seen a similar sequence defined before where the distance was $|x_n - x_{n+1}| = \frac{1}{2^{n-1}}$.

Would appreciate tips on defining the recurrence and whether my idea on solving this is even correct / a different approach.

Answer 1

You can find $\alpha$ and $\beta$ such that $$x_n = \alpha^n C_1+ \beta^n C_2.$$ From this you can conclude that $|x_m-x_n| = |(\alpha^m-\alpha^n)C_1 +(\beta^m-\beta^n)C_2 |\leq C\gamma^m$ for a suitable $\gamma$ and constant $C.$

See how to find $\alpha$ and $\beta$ here:

http://discretetext.oscarlevin.com/dmoi/sec_recurrence.html

Answer 2

First observe that : $|a_{n+1} - a_n| = \left|\dfrac{1}{3}a_n+\dfrac{2}{3}a_{n-1} - a_n\right|=\dfrac{2}{3}\left|a_n - a_{n-1}\right|= c|a_{n}-a_{n-1}|=c^2|a_{n-1}-a_{n-2}|=\cdots = c^k|a_{n-k+1}-a_{n-k}|= c^{n-1}|a_2-a_1|=c^{n-1}\implies |a_m-a_n|= |a_m - a_{m-1} + a_{m-1}-a_{m-2} +\cdots +a_{n+1} - a_n|\le |a_m- a_{m-1}|+|a_{m-1} -a_{m-2}|+\cdots +|a_{n+1}-a_n| \le c^{m-2}+c^{m-3}+\cdots + c^{n-1}= c^{n-1}(1+c+c^2+\cdots + c^{m-n-1})= c^{n-1}\left(\dfrac{1-c^{m-n}}{1-c}\right)\le \dfrac{c^{n-1}}{1-c}=3c^{n-1}$. Since $0 < c < 1, c^{n-1} \to 0$ as $n \to \infty$, $\exists N \ge 1$ such that $3c^{n-1} < \epsilon$ whenever $n \ge N$. Thus if $m, n \ge N\implies |a_m - a_n| < \epsilon$, proving$\{a_n\}$ a Cauchy sequence.

Answer 3

Hint: $\mid x_n-x_m\mid\le (\frac23)^{n-m} \mid x_{m+1}-x_m\mid=(\frac23)^n\mid x_2-x_1\mid=(\frac23) ^n$.

Answer 4

Suppose $u_{n+2} = c u_{n+1}+(1-c)u_n$ where $0 < c < 1$.

The characteristic polynomial is $x^2 = cx + (1-c) $ or $x^2 - cx - (1-c) $ or $x =\dfrac{c\pm\sqrt{c^2+4(1-c)}}{2} =\dfrac{c\pm\sqrt{c^2-4c+4}}{2} =\dfrac{c\pm\sqrt{(c-2)^2}}{2} =\dfrac{c\pm(c-2)}{2} =1, c-1 $

The solutions are therefore $u_n =a+b(c-1)^n $ for some $a$ and $b$.

This is all you need to show that it is Cauchy.

If $u_0 = r, u_1 = s$ then $r = a+b, s = a+b(c-1) $ so $s-r =b(c-1-1) =-b(2-c) $ so $b = -\frac{s-r}{2-c} = \frac{r-s}{2-c} $ and $a =r-b =r-\frac{r-s}{2-c} =\frac{r(2-c)-r+s}{2-c} =\frac{r(1-c)+s}{2-c} $.

Since $\lim_{n \to \infty} (c-1)^n = 0$, $\lim_{n \to \infty} u_n =a =\frac{r(1-c)+s}{2-c} =\frac{u_0(1-c)+u_1}{2-c} $.

Here $c = \frac13, u_0 = 0, u_1 = 1$ so $a = \frac{1}{2-\frac13} = \frac{1}{\frac53} = \frac35 $.