Suppose we have a linear recurrence relation

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


  • $(\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.

  • $\begingroup$ An older (and fully answered) question of mine deals with the case $y_n=0$. I haven't looked at the details, but my guess is that the method described therein carries through to your case. $\endgroup$ Feb 2 '21 at 9:44
  • 1
    $\begingroup$ What a well-asked question! Indeed, this case should follow similarly; I was thinking of operator norms rather than diagonalisations, and one examines a sum of exponentially decaying terms rather than just one. A bounty to she that provides the details, arrr! $\endgroup$
    – Good Boy
    Feb 2 '21 at 10:16
  • $\begingroup$ Sorry I edited the OP by mistake instead of editing my answer $\endgroup$ Feb 2 '21 at 17:26
  • $\begingroup$ That's both hilarious and rectifiable. $\endgroup$
    – Good Boy
    Feb 2 '21 at 17:29
  • $\begingroup$ Thanks for rectifying it ! I was a little bit embarassed ... I guess that with great foresight you had saved the content somewhere $\endgroup$ Feb 2 '21 at 17:30

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


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)$


$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}$.

  • $\begingroup$ Pretty neat! Thanks for the answer and reference. Out of interest, do you know if there are results which apply in the renewal setting (where the recursion involves infinitely many terms)? $\endgroup$
    – Good Boy
    Feb 7 '21 at 12:39
  • $\begingroup$ I do know some results along those lines. I was having trouble finding a journal interested in the concept though, so I never published them. This now makes it difficult to point you to a nice authoritative source. I haven't seen anyone else deal with those infinite order cases. There was one gentleman Stevo Stevic' who would analyze many generalized cases. So I could tell you to look among his papers. If there is a real interest I could put together a submission. Where does the problem arise by the way? $\endgroup$ Feb 9 '21 at 14:29
  • $\begingroup$ The problem arises in a silly setting: proving that the distribution of gaps in the Kakutani–Fibonacci sequence of partitions converges to $(2-2x)\mathrm dx$, by a moment method. It follows directly from equidistribution, as it turns out. The infinite case would be of potential application in another project $\endgroup$
    – Good Boy
    Feb 19 '21 at 9:57

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$.

  • 1
    $\begingroup$ Thanks for you answer Ewan! Indeed, one should not expect that the convergence is to zero. However, is this method not enough to conclude a Cauchy property for the $(w_n)$? (Particularly as it seems $w_n$ can be compared to the partial sums of an absolutely convergent series.) $\endgroup$
    – Good Boy
    Feb 2 '21 at 11:43

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.