Show that the sequence $x_{n+1}=5x_n-4x_{n-1}$ diverge

Question

Show that the sequence $(x_n)$ defined as $x_{n+1}=5x_n-4x_{n-1}$ with $x_0=0,x_1=1$ diverge.

It is clear that the sequence diverge and this sequence is not really interesting, but still i'd like to know if my proof is correct (can't complete).

Suppose by absurd that the sequence $(x_n)$ converge and is a Cauchy sequence. So by définition we must have:

$\forall \varepsilon>0 \ \exists N \ \forall m,n\ge N$ $(m>n)$: $|x_m-x_n|<\varepsilon$

Moreover, $\forall p>1$: $|x_p-x_{p-1}|=|4(x_{p-1}-x_{p-2})|=...=|4^{p-1}|$

So we have that $|x_m-x_n|\le|x_m-x_{m-1}|+|x_{m-1}+x_{m-2}|+...+|x_{n+1}-x_n|\le 4^{m-1}+4^{m-2}+...+4^{n}=\sum_{k=n}^{m-1}4^k$

and so the sequence $(x_n)$ is not Cauchy.

The last line i'm not sure how to conclude correctly (if everything that i've done till now is correct) so need help and correction please! Thanks in advance

Answer 1

Your proof is not correct.

Unfortunately you missed the fact that

$$\vert x_p -x_{p-1} \vert =4^{p-1} \vert x_1 -x_0 \vert$$ is enough to prove that the sequence is not Cauchy (providing that $x_1 \neq x_0$).

You have proven that $\vert x_m -x_n \vert$ is less than a diverging term and concluded that the sequence is not Cauchy. This is where the error lies: being less that something that diverges is saying nothing on the convergence.

Also, you should be more precise $$|x_p-x_{p-1}|=|4(x_{p-1}-x_{p-2})|=...=|4^{p-1}|$$ is not correct. The difference depends on the difference of the two first terms of the sequence.

Answer 2

You mean given $\varepsilon > 0$, the assumption to the contrary gives $N\in\mathbb{N}$ such that $\forall m,n > N\implies |x_m-x_n|<\varepsilon$ right? So to finish it off, you can just show that for some $m,n >N,$ this cannot hold. An obvious candidate would be $n = N+1$ and $m = N+p$ and you can take $p$ as large as you want.

How large? If you want to be explicit, then evaluate the geometric sum and play around with the logarithms. Or heuristically, you can say that the geometric series obviously diverges, no matter where it starts since $4 > 1.$

Answer 3

$$X_{n+1}=5X_n-4X_{n-1}$$ Let $X_n=t^n$, then

$$t^{n+1}-5t^{n-1}+4t^n=0 \implies t^2-5t+4=0 \implies t=2,3$$ So $$X_n=p 2^n + q 3^{n} \implies X_n=-2^n+3^n \implies \lim_{n \to \infty} X_n=\infty.$$