A sequence $a_n$ is said to be polynomially recursive (P-recursive) if it satisfies:

$$p^{[r]}(n)a_{n+r}+\cdots+p^{[1]}(n)a_{n+1}+\cdots + p^{[0]}(n)a_n=0$$

where $p^{[i]}(t)\in \mathbb{Q}[t]$ are polynomials with rational coefficients, with $p^{[0]},p^{[r]}$ not identically zero.

For example, $a_n:=n!$ is one such sequence since: $2a_{n+2}-(n+2)a_{n+1}-(n+1)(n+2)a_n=0$, with initial conditions $a_0:=0, a_1:=1$.

Fix a set of polynomials $\{p^{[i]}(t)\}_{i=0}^r$, and suppose $a_n,b_n$ are a pair of sequences that satisfy the same above recurrence, with different initial conditions. Furthermore, suppose that both sequences aren’t ultimately periodic or constant.

Define $L :=\lim_{n\rightarrow\infty} \frac{a_n}{b_n}$.

Main Question: Is it obvious when $L\in (0,\infty)$? In other words, when does $L$ exist, is non-zero and non-infinite? Aside from numerically evaluating the limit for large enough $n$, are there any algorithmic methods for deducing that $L \in (0,\infty)$?

There are many known (non-trivial) results about the growth rates of such sequences, for example results due to Poincaré, Birkhoff and Trjitzinsky, Wimp and Zeilberger, and Mezzarobba and Salvy. However, I'm unable to find good references related to my question, especially as a function of initial conditions. The main difficulty I have is that I’m not sure how to find good lower bounds on the growth rates of such sequences.

  • $\begingroup$ You probably assume $p^{[r]},p^{[0]}\neq 0$. $\endgroup$
    – YCor
    Jan 12, 2021 at 9:12
  • $\begingroup$ I am really not familiar with this topic, but I took a look at your reference by Mezzarobba and Salvy. Their method seems to use the initial values only for the computation of the constant factor of the upper bound, and they said that their bound is generically tight (I don't know what it means). Doesn't these two facts imply that your main question holds at least generically? $\endgroup$
    – Hhan
    Jan 12, 2021 at 10:51
  • $\begingroup$ @YCor: yes. Technically if $p^{[0]}(n)$ has positive integer zeros, then we need additional initial conditions to ensure uniqueness. $\endgroup$
    – Alex R.
    Jan 12, 2021 at 18:31
  • $\begingroup$ @Hhan: thanks for your observation. I’m still trying to make sense of that paper but part of the issue seems that they only have an upper bound so I’m not sure if that would be enough to conclude what happens to my ratio. $\endgroup$
    – Alex R.
    Jan 12, 2021 at 18:34
  • 1
    $\begingroup$ Note that $L$ need not exist, even for constant coefficients when the associated (characteristic) polynomial is irreducible, e.g., $a_{n+2}+a_{n+1}+a_n=0$, with initial conditions $a_0=1, a_1=-1$ and $a_0=0, a_1=1$. $\endgroup$ Jan 18, 2021 at 2:25

1 Answer 1


This is a difficult question in general; see for instance

for recent work on special cases. (As you noted, the paper by Bruno Salvy and myself that you mention is purely about upper bounds and thus not terribly relevant.)

However, there are sufficient conditions for $L$ to be nonzero and finite that can be verified algorithmically and cover a fair number of (“easy”) cases. In particular, by passing to the differential equation on the generating series, one may be able to get “asymptotic expansions with error bounds” of the form, say, $|a_n - α f(n)| ≤ g(n)$, $|b_n - β f(n)| ≤ h(n)$ where $f$, $g$, $h$ are explicit functions with $g, h = o(g)$ and $α$, $β$ are constants that can be bounded from both sides. For more details on this kind of ideas, see for example


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.