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!

  • $\begingroup$ how $\lim_{n\to\infty}|x_{n+1} -x_n|=0 $ will ensure that limit of sequence will exist ? $\endgroup$ – neelkanth Feb 6 at 17:02
  • $\begingroup$ @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$ $\endgroup$ – roman Feb 6 at 17:25
  • $\begingroup$ You could have tried characteristic polynomial method indeed, e.g. very similar question here $\endgroup$ – 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$


  • $\lambda=-2$


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.

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

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.