"Approximating" linear recursion with homogenous polynomial coefficients by linear recursion with constant coefficients

Question

In a lecture I once attended, I remember the speaker using a result of the following nature:

$``$Let $\{A_n\}_{n=1}^\infty \subset \mathbb R$ be a sequence satisfying a recursion of the form
$$P(n) A_n + Q(n) A_{n-1} + R(n) A_{n-2} = 0 \hspace{6mm} \text{ for all } n \geq 0$$ where $P, Q, R \in \mathbb Q[T]$ are polynomials having the same degree with leading coefficients $p, q, r>0$ respectively. Consider the sequence $\{C_n\}_{n=1}^\infty \subset \mathbb R$ satisfying the linear recursion $$pC_n + qC_{n-1} + rC_{n-2} = 0. \hspace{6mm} \text{ for all } n \geq 0$$ such that $C_0=A_0$ and $C_1=A_1$. Suppose for convenience, that all of the $A_n$ and $C_n$ are positive. Then $$A_n \sim C_n\text{ as }n \rightarrow \infty."$$

While in the special case considered in the lecture, it was still easy to verify the claim, I feel like this is something which should also be true in the general setting described above, however I am unable to prove the same. I tried considering the sequence $r_n:=A_n/C_n$ and obtained a recursion for $r_n$ which also involved terms of the sequence $y_n:=C_n/C_{n-1}$ (which itself clearly satisfies the recurrence $py_n + r/y_{n-1} + q = 0$ and furthermore has an explicit expression coming from standard solutions of linear recurrences), I end up running into the issue of showing that the sequence $\{r_n\}_{n=1}^\infty$ is bounded - even though it seems so intuitively obvious. Am I missing something (probably really trivial observation) in the proof or is there some additional hypothesis that needs to be imposed?

I also feel like this should generalize further to '$k$-th order' linear recurrences: meaning those of the form $\sum_{j=0}^k P_j(n) A_{n+j} = 0$ for all $n \geq 0$, where $P_0, \cdots , P_k \in \mathbb R[T]$ are predetermined polynomials, all of the same degree. Is that too naïve to expect? If not, can I go about proving this (maybe with some mild additional hypotheses) without going into too heavy or technical computations? I would really like to know the answer to both of these questions that I have been pondering over for quite a while. Thanks a lot.

Edit: Thanks to Iosif Pinelis' nice counterexample, I am understanding a little better why my attempt for the general case wasn't working. So let me give another set of exact polynomials $P, Q, R$ I want to check the above result for: it is $$P(n):=n^3, \hspace{5mm} Q(n):=-(34n^3-51n^2+27n-5), \hspace{5mm} R(n):=(n-1)^3.$$ This is an example that I have been wrestling with to no avail and would really appreciate some help to that end.

Edit 2: Can we at least say $A_n \asymp C_n$, - given initial conditions $A_0=1, A_1=5$ and with $C_j$ set to appropriate ones, - in the above scenario? Perhaps the recursion for $C_n$ would be something "like" (but not exactly the same as) $$C_n=34C_{n-1}-C_{n-2} \tag{1},$$ in the sense that $C_j$ would satisfy a second order linear recurrence whose characteristic polynomial would have two real roots, with the larger (positive) one pretty 'close' to $(\sqrt 2 + 1)^4$, - the larger root of the characteristic polynomial of $(1)$?

Answer 1

You need a number of additional conditions here for such a statement to hold. For one thing, equation $pC_n+qC_{n-1}+rC_{n-2}=0$ has infinitely many solutions, depending on initial conditions (say). Even if that is taken care of, the condition that $P,Q,R$ are polynomials having the same degree with leading coefficients $p,q,r>0$ is not enough.

Consider the following counterexample, for simplicity with a recursion of depth $1$ rather than $2$, with two polynomials, $P(n)=n$ and $Q(n)=n-1$, so that $p=q=1$, $nA_n+(n-1)A_{n-1}=0$, and $C_n+C_{n-1}=0$. Then $(-1)^nnA_n=c$, a constant, so that $A_n=(-1)^nc/n$, whereas $C_n=(-1)^n b$ for some real $b$ and all $n$, so that $A_n\not\sim C_n$.

---

Concerning the particular example in your Edit's, after one goes through all the motions prescribed in Theorem 1 (part 1) and Remark 4 in this paper or its freely available, report version, one concludes that $A_n/C_n=O(1/n^{3/2})$ (with any initial conditions on $(A_n)$). This conclusion is illustrated (for $A_0=C_0=1,A_1=C_1=5$) by the following image of a Mathematica notebook, which suggests that, moreover, $A_n/C_n\sim b/n^{3/2})$ for some real constant $b>0$ (click on the image to enlarge it):