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.

9more comments