3
$\begingroup$

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

$\endgroup$
3
  • 1
    $\begingroup$ 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$. $\endgroup$ Oct 22 '20 at 0:14
  • $\begingroup$ @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... $\endgroup$
    – asrxiiviii
    Oct 22 '20 at 0:58
  • $\begingroup$ ... or (I reckon) for any non-obvious recursion which can't be "unrolled" in $\asymp \log n$ steps. $\endgroup$
    – asrxiiviii
    Oct 22 '20 at 1:03
3
$\begingroup$

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

enter image description here

$\endgroup$
8
  • $\begingroup$ 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! $\endgroup$
    – asrxiiviii
    Oct 20 '20 at 1:11
  • 1
    $\begingroup$ @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. $\endgroup$ Oct 20 '20 at 2:46
  • 1
    $\begingroup$ @asrxiiviii : Plotting suggests that in the particular example in your (first) Edit, $A_n/C_n=O(1/n)$, just as in my counterexample. $\endgroup$ Oct 20 '20 at 17:15
  • 1
    $\begingroup$ @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. $\endgroup$ Oct 21 '20 at 21:08
  • 1
    $\begingroup$ @asrxiiviii : Your conjecture $A_n\asymp C_n$ has now been rigorously disproved, with the help of a general result found in the literature. $\endgroup$ Oct 23 '20 at 3:49

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.