What is the general method for finding the aymptotics of large $n$ of the sequence $(a_n)_{n=0}^\infty$ defined by the recursion $$a_{n} = (\alpha_1n+\alpha_2) a_{n-1} + (\alpha_3n+\alpha_4) a_{n-2}+\delta \tag1$$ where $\alpha_i$'s are constant real numbers and $\delta\in\{0,1\}$ is constant.

Here is an example of the above recursion and my frustrated attempt at using the generating function for the un-simplified version. That particular example is solvable with a generating function once it is transformed. However, not every recursion of the form $(1)$ can be simplified through a simple transformation.

  • $\begingroup$ Did you try generating functions? $\endgroup$ Oct 11, 2019 at 6:02
  • $\begingroup$ @IlyaBogdanov: Yes, I did indeed. I added the link to my frustrated attempt at an example. $\endgroup$
    – Hans
    Oct 11, 2019 at 6:57
  • $\begingroup$ is $\delta\in \{0,1\}$ fixed or may depend on $n$? $\endgroup$ Oct 11, 2019 at 7:30
  • $\begingroup$ @FedorPetrov: Just clarified that in the question. $\endgroup$
    – Hans
    Oct 11, 2019 at 7:46
  • $\begingroup$ $C.n!\alpha_1^nn^{\alpha_2/\alpha_1+\alpha_3/\alpha_1^2}$ I believe if $\alpha_1\alpha_3\ne0$ (similar formulas otherwise). $\endgroup$ Oct 11, 2019 at 8:36

1 Answer 1


I do not know about the general method, but here's a recipe for $\delta = 0$.

One can view this as a 3-term recurrence relation, and consider the corresponding orthogonal polynomials. Favard's Theorem guarantees such polynomials exist, and in fact Riesz Representation Theorem upgrades the orthogonality to the usual one if you ensure $\alpha_3 n + \alpha_4 < 0$. This transfers the problem to a problem to a problem about asymptotics of orthogonal polynomials, which can be done using multiple methods (WKB, Riemann-Hilbert, amongst many others).


Consider $\alpha_1 = 0, \ \alpha_2 = 2, \ \alpha_3 = -2, $ and $\alpha_4 = 2$. Then, assuming no algebra mistakes, we have (I re-index so I can use Wikipedia) $$ a_{n + 1} = 2a_n - 2na_{n - 1}, \ a_0 = 1, \ a_2 = 2 $$ This recurrence is satisfied by Hermite polynomials $H_n(x)$ (evaluated at $x = 1$), which satisfy $$ \int_{-\infty}^{\infty} x^k H_n(x) \ e^{x^2} = 0 \quad \text{ for } k = 0, 1, ..., n-1. $$ and $$ H_{n + 1}(x) = 2xH_n(x) - 2nH_{n - 1}(x) $$ Now, again the wikipidia page tells me that (this I did not check too carefully, but I know asymptotic expansions of Hermite Polynomials exist) $$ a_n = H_n(1) \sim e^{1/2} \dfrac{2^n}{\sqrt{\pi}} \Gamma\left( \dfrac{n + 1}{2} \right) \cos \left( \sqrt{2n} - \dfrac{n \pi}{2} \right). $$

Now, in the general situation, a glance at Chihara's book "Introduction to Orthogonal Polynomials" (Pages 215 - 217) tells me that for recurrences of the form you give will often be handled using Hermite and Charlier polynomials (maybe others if you get funny about what $x$ value you consider).

P.S. I am new to this, so if this needs downgraded to a comment or is somehow not what you wanted, my bad!

  • 1
    $\begingroup$ +1. Very clever connection to the orthogonal polynomials! Short of the treatment for $\delta=1$, it is a full solution. $\endgroup$
    – Hans
    Oct 12, 2019 at 3:00

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.