The asymptotics of a recursion

by Hans   Last Updated October 10, 2019 03:20 AM - source

I am trying to assess the aymptotic behavior for large $n$ of the sequence $(a_n)_{n=0}^\infty$ defined by the recursion $$a_{n} = (n+1) a_{n-1} - n a_{n-2}-1.$$ Define the generating function $f(x):=\sum_{n=0}^\infty a_nx^n$. $g(x):=x^2f(x)$ satisfies the ODE $$g'-\Big(\frac1{x^2}+\frac1x+\frac1{1-x}\Big)g=\Big(\frac x{1-x}\Big)^2-\frac{a_0}{1-x}+(2a_0-a_1)\frac x{1-x}$$ Multiply both sides by $e^h=\frac{1-x}xe^{\frac1x}$ where $h(x):=\frac1x+\ln\frac{1-x}x$ and get $$\frac{d}{dx}\Big(\frac{1-x}xe^{\frac1x}g\Big)=e^{\frac1x}\Big(\frac x{1-x}-\frac{a_0}x+(2a_0-a_1)\Big).$$ Now $e^{\frac1x}$ seems to prevent me from solving the ODE in a "closed" form.

I read somewhere the complex analysis may help to derive the large $n$ asymptotics of $a_n$. How does one procede?

Answers 1

Partial answer to an interesting problem. However, without $a_0$ and $a_1$ specified, one can't even determine the sign of the asymptotics. By dropping the -1 on the right-hand side of the equation, the recursion can be solved (in Mathematica) in terms of 'subfactorials.' That is

$$a_n = \kappa_1+ \kappa_2 \sum_{k=0}^n k! $$

where the $\kappa$ are related somehow to $a_0$ and $a_1.$ Naturally the second term will dominate. Choosing $a_0=0$ and using numerical and symbolic computations I was able to determine

$$ a_n \sim (a_1+2-e)\sum_{k=0}^n k! \quad ,\quad (a_0 = 0)$$

To make it absolutely clear, this step lacked rigor. The sum may be approximated by $ \sum_{k=0}^n k! \sim n! (n-1)/n .$ As a check, for $a_1=2,$ by the time $n=10,$ the relative error is about 1 part in a million. What would be an interesting study is what happens to the asymptotics when $a_1 = e-2;$ it appears to be slowly growing, like $\cal{o}(n^{1/4}).$ We therefore have a region where, even with one constant simply specified, a non-uniformity appears. With two free constants, this problem might be a real bear to get a handle on.

October 10, 2019 02:55 AM

Related Questions

Hypergeometric function at $z=1$

Updated August 29, 2019 21:20 PM

Closure in an ODE for a generating function

Updated October 11, 2017 21:20 PM

Generating function ODEs: closure condition

Updated October 17, 2017 17:20 PM

Find range of $k$ where $y = k$ is an asymptote

Updated May 16, 2019 02:20 AM