Linear recursion with convergent coefficients

Question

Suppose we have a linear recurrence relation

$$x_n = \alpha_n x_{n-1}+ \beta_n x_{n-2} + y_n,$$

where

• $(\alpha_n) \to \alpha >0$,
• $(\beta_n) \to \beta >0$,
• $(y_n) \to y > 0$, and
• the limiting auxiliary equation, $m^2 - \alpha m - \beta$, has roots in $(-1,1)$

(all limits are as $n \to \infty$).

My question:

Does this imply that the sequence $(x_n)_{n=1}^\infty$ converges?

This comes from a convergent example. I am simply wondering if the above information suffices to prove it, or if one needs control on the rates of convergence, say.

Answer 1

There is a nice order reduction result for difference inequalities in the following reference which simplifies the reasoning quite a bit:

https://msp.org/involve/2008/1-1/p07.xhtml

For a given $\epsilon > 0$, for sufficiently large N, we have that for $n>N$:

$$(\alpha + \beta -\epsilon)min(x_{n-1}, x_{n-2}) + (\gamma - \epsilon) \leq x_{n} \leq (\alpha + \beta +\epsilon)max(x_{n-1}, x_{n-2}) + (\gamma + \epsilon).$$

The condition on the roots ensures $\alpha + \beta < 1$.

Applying theorem's 2 and 3 from the reference we can bound solutions of the recursion $x_{n}$ between the following two recursions (taking maxes over chains of terms as shown in the article):

$u_{n} = (\alpha + \beta -\epsilon) u_{n-1} + (\gamma - \epsilon)$

and

$v_{n} = (\alpha + \beta +\epsilon) v_{n-1} + (\gamma + \epsilon)$

Since $\alpha + \beta < 1$ both {$u_{n}$} and {$v_{n}$} converge to the unique equilibrium.

Therefore given $\epsilon_{2} > 0$ there exists $M$ so that for $n>M$:

$$\frac{\gamma - \epsilon}{1-\alpha -\beta + \epsilon} - \epsilon_{2} \leq x_{n} \leq \frac{\gamma + \epsilon}{1-\alpha -\beta - \epsilon} + \epsilon_{2}$$

Thus $x_{n} \to \frac{\gamma}{1 - \alpha - \beta}$.

Answer 2

The answer to your question is YES ; in fact, I show below that $(x_n)$ always converges to $l=\frac{y}{1-(\alpha+\beta)}$ (notice that $1-(\alpha+\beta)\neq 0$, otherwise $1$ would be a root of $m^2-\alpha m -\beta$).

First, let us see what happens when we adapt the method in the answer to the linked question.

The scalar recursion of order 2 is equivalent to the following recursion of order 1 for vectors via $v_n=(x_n,x_{n+1})^T$. \begin{equation}\tag{1}\label{one} v_{n+1}=A_nv_n+C_n,\ \ A_n=\left(\begin{matrix}0&1\\ \beta_{n+2}& \alpha_{n+2}\end{matrix}\right) \ C_n=\left(\begin{matrix}0\\y_{n+2}\end{matrix}\right) \end{equation} If $\lambda,\mu$ are the roots of $m^2-\alpha m-\beta$ which satisfy $|\lambda|,|\mu|<1$ by assumption then there is a constant matrix $T$ such that $$\newcommand{\eps}{\varepsilon}T^{-1}A T= \left(\begin{matrix}\lambda&\eps\\0&\mu\end{matrix}\right)=:D \mbox{ for }A=\lim A_n=\left(\begin{matrix}0&1\\ \beta & \alpha \end{matrix}\right)$$ where $\eps=0$ unless $\lambda=\mu$ and the eigenvalue $\lambda$ of $A$ has algebraic multiplicity 1; in this case $\eps\neq0$ and it can be chosen such that $|\lambda|+|\eps|<1$. Putting $v_n=Tw_n$ transforms (\ref{one}) to $$w_{n+1}=(D+F_n)w_n+ C'_n,$$ where $F_n$ is a matrix of elements tending to 0 and $C'_n=T^{-1}C_n$ is a column matrix tending to a finite limit when $n\to \infty$.

Using the maximum norm for vectors and the corresponding matrix norm, we find $$||w_{n+1}||\leq\big(\max(|\lambda|+|\eps|,|\mu|)+||F_n||\big)||w_n||+||C'_n||.$$

By assumption, the maximum is smaller than 1 and $||F_n||$ tends to 0. Also $(||C'_n||)$ is bounded. Therefore there exist some $0<M<1$, some $C\gt 0$ and some integer $N$ such that the big parenthesis is $\leq M$, and $||C'_n|| \leq C$ for $n\geq N$. This means that $$||w_{n+1}||\leq M||w_{n}||+C\mbox{ for }n\geq N$$ and hence $||w_n||\leq ||w_N|| M^{n-N} + C(1+M+M^2+\ldots+M^{n-N}) \leq ||w_N|| M^{n-N} + \frac{C}{1-M}$ for $n\geq N$ :

$$ ||w_n||\leq ||w_N|| M^{n-N} + \frac{C}{1-M} \tag{2}\label{two} $$ Therefore $w_n$ is bounded and therefore also $v_n$ and $x_n$.

Now, if we put $x'_n=x_n-l$, we have

$$ x'_{n}=\alpha_n x'_{n-1}+ \beta_n x'_{n-2} + y'_n $$

where $y'_n=y_n-(1-\alpha_n-\beta_n)l$ tends to zero. Redoing all our preceding computations with $(x'_n)$ in place of $(x_n)$, we obtain a sequence $||w'_n||$ satisfying an analogue of $\eqref{2}$ where the constant $C$ can be arbitrarily small when $N$ is large enough. This shows that $(w'_n)$ converges to zero, and hence that $(x_n)$ converges to $l$.