# Verification (and help) with the questions related to convergence of recurrences in the form $x_{n+2} = kx_{n+1} + px_n$

Given $$x_1 = a$$ and $$x_2 = b$$ find the values of $$a, b \in \Bbb R, n\in\Bbb N$$ for which the following recurrences converge (diverge): \begin{align*} x_{n+2} &= 2x_{n+1} - x_n \tag1\\ x_{n+2} &= 4x_{n+1} - 3x_n\tag2\\ x_{n+2} &= -2x_{n+1} - x_n\tag3\\ x_{n+2} &= x_{n+1} + 2x_n\tag4\\ \end{align*}

$$(1)$$: \begin{align} x_{n+2} &= 2x_{n+1} - x_n \iff \\ x_{n+2} - x_{n+1} &= x_{n+1} - x_n = \\ &= x_{n+1} - x_{n}\\ &= x_{n} - x_{n-1}\\ &\cdots\\ &= x_{2} - x_{1}\\ &= b - a \end{align} Now taking the limit: $$\lim_{n\to\infty}(x_{n+1} - x_{n}) = \lim_{n\to\infty}(a-b)=a-b$$ For this recurrence to be convergent $$a$$ must be equal to $$b$$, otherwise it doesn't satisfy Cauchy criteria, thus: $$a = b \implies \exists \lim_{n\to\infty}x_n \\ a \ne b \implies \exists! \lim_{n\to\infty}x_n$$

$$(2)$$: \begin{align} x_{n+2} &= 4x_{n+1} - 3x_n \iff\\ x_{n+2} - x_{n+1} &= 3(x_{n+1} - x_n) \\ &= 3^2(x_{n} - x_{n-1})\\ &\cdots \\ &= 3^{n-1}(x_{2} - x_{1})\\ &= 3^{n-1}(b - a) \end{align}

This case is similar to $$(1)$$: $$b = a \implies \exists \lim_{n\to\infty}x_n\\ b \ne a \implies \exists! \lim_{n\to\infty}x_n$$

$$(3)$$: \begin{align} x_{n+2} &= -2x_{n+1} - x_n \iff \\ x_{n+2} + x_{n+1} &= -(x_{n+1} + x_n) \\ &= (x_{n} + x_{n-1}) \\ &= -(x_{n-1} + x_{n-2}) \\ &\cdots\\ &= (-1)^{n-1}(x_2 + x_1) \\ &= (-1)^{n-1}(b + a) \\ \end{align}

In this case convergence is only possible if: $$a + b = 0 \implies \exists \lim_{n\to\infty}x_n\\ a + b \ne 0 \implies \exists! \lim_{n\to\infty}x_n$$

$$(4)$$. I'm stuck with this one, not sure what transformations to apply. I could probably use generating functions or solve through a characteristic polynomial, but that is heavy machinery for such a simple case. I would also like to not apply any solutions involving matrices since i'm not very familiar with linear algebra yet.

Could you please verify the first three cases and either suggest a solution or give a hint for the last one? Thank you!

• how $\lim_{n\to\infty}|x_{n+1} -x_n|=0$ will ensure that limit of sequence will exist ? – neelkanth Feb 6 at 17:02
• @neelkanth well, it might not, i'm not sure. However if we choose some $C\in\Bbb R^+$ and $\lambda \in (0,1)$ such that $|x_{n+1} - x_n| = |a - b| \le C\lambda^n$ then $x_n$ converges. And this seems to only be possible for $a-b = 0$ – roman Feb 6 at 17:25
• You could have tried characteristic polynomial method indeed, e.g. very similar question here – rtybase Feb 25 at 21:02

The first two points are correct (but you need to justify $$a= b \implies (x_n) \text{ is convergent}$$).

For the third point $$x_{n+1}+x_n=0$$ for all $$n$$ does not ensure that $$(x_n)$$ is convergent. In fact it leads to $$x_{n+1}=-x_n$$ so $$x_n=(-1)^{n-1} a = (-1)^{n-2} b$$ so the condition is $$a+b=0 \text{ and } a=b=0$$.

For the last point in you want to applies a similar method the best way is to define $$y_{n}=x_{n+1}+\lambda x_n$$ where $$\lambda$$ is a parameter we will choose later.

In this case we have $$y_{n+1}=x_{n+2}+\lambda x_{n+1}=x_{n+1}+2x_n+\lambda x_{n+1}\\=(1+\lambda)\left(x_{n+1}+\frac{2}{1+\lambda} x_n \right).$$

So by choosing $$\lambda$$ such that $$2/(1+\lambda)=\lambda$$ i.e $$\lambda=1$$ or $$\lambda=-2$$ we obtain

• $$\lambda=1$$

$$(x_{n+2}+x_{n+1})=2(x_{n+1}+x_n)$$

• $$\lambda=-2$$

$$(x_{n+2}-2x_{n+1})=-(x_{n+1}-2x_n)$$

so you obtain a necessary condition for convergence $$b+a=0$$ $$b-2a=0$$ and so the sequence is convergent iff $$a=b=0$$.

Note that by considering a generic recurrence you can show that the good choice of $$\lambda$$ are always the opposite of the roots of the characteristic polynomial.

• Nice approach for the last case. Thank you! – roman Feb 25 at 18:52