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

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

• Do you really need that $C_n$ have the same initial conditions of $A_n$? I think it is more likely to be true that $A_n\sim C'_n$ for a suitable solution $C'_n$ of the Linear Recursion with Constant Coefficients, not necessarily the one with the same initial conditions of $A_n$. Oct 22, 2020 at 0:14
• @Pietro Majer Yes I think so too: there should be some $\alpha$ close, but not exactly equal, to $(\sqrt 2 + 1)^4$ (i.e. the bigger root of the characteristic equation of the linear recurrence $C_n=34C_{n-1}-C_{n-2}$), such that $C_n \sim \alpha^n$, I'm just trying to figure out what $\alpha$ would be. This is why in a comment in Iosif Pinelis' answer, I also asked for software which gives asymptotic bounds like Wolfram Alpha (wolframalpha.com/input/…) can do, as it can't do the same for my recursion... Oct 22, 2020 at 0:58
• ... or (I reckon) for any non-obvious recursion which can't be "unrolled" in $\asymp \log n$ steps. Oct 22, 2020 at 1:03

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):
• Nice! Can you also look into the above edit? Also as a curiosity, are there any minimal sufficient conditions (say on my sequence $\{A_n\}_{n=1}^\infty$ and/or polynomials appearing as coefficients etc.) guaranteeing the kind of result I want? I feel like "approximating" such linear recurrences with same degree polynomial coefficients by those with constant coefficients is something that should have been done before, but I can't find any literature. Do you know some references to that end? Thanks again! Oct 20, 2020 at 1:11
• @asrxiiviii : If by $A_n\sim C_n$ you mean $A_n/C_n\to1$ (as is usually done), then the above example strongly suggests that $A_n\sim C_n$ will almost never hold. If by $A_n\sim C_n$ you mean $|A_n/C_n+C_n/A_n|$ is bounded, then I think there a chance for that if $P(n)=pn^k(1+O(1/n^2))$, $Q(n)=qn^k(1+O(1/n^2))$, etc. In any case, as I said before, you need to specify appropriate initial conditions. Oct 20, 2020 at 2:46
• @asrxiiviii : Plotting suggests that in the particular example in your (first) Edit, $A_n/C_n=O(1/n)$, just as in my counterexample. Oct 20, 2020 at 17:15
• @asrxiiviii : I have added the mentioned plotting. I think I could prove rigorously that in your example $A_n\not\asymp C_n$, but am afraid that the effort to prove such a negative statement -- very likely to be true, but apparently not fulfilling your desire -- would be misplaced. Oct 21, 2020 at 21:08
• @asrxiiviii : Your conjecture $A_n\asymp C_n$ has now been rigorously disproved, with the help of a general result found in the literature. Oct 23, 2020 at 3:49