Combinatorics – Asymptotics of a Quadratic Recursion

co.combinatoricsinequalitiesreal-analysisreference-requestsequences-and-series

Consider the sequence defined by
\begin{align}
c_0 &{}= 1 \\
c_n &{}= 2\,n\,c_{n-1}-\frac{1}{2}\sum_{m=1}^{n-1}c_m\,c_{n-m}.
\end{align}

How can you prove that it has the following asymptotics (strongly suggested by numerics)
$$
c_n\sim \frac{2}{\pi}\Gamma(n)\,2^n\ \ \ ?
$$

To make the question more motivated: the associated divergent series is the asymptotic expansion of a simple ratio of modified Bessel functions
$$
R(z) = \frac{K_0(-\frac{1}{4z})}{K_1(-\frac{1}{4z})}\sim \sum_{n\ge 1}c_n z^n = 1+2z+6z^2+24z^3+\dotsb.
$$

Indeed, as pointed out in the comment by Richard Stanley, one has
$$
4z^2 R'+4z R+1-R^2 = 0.
$$

So the question boils down to what can be said about the large order behaviour of the terms of the asymptotic expansion of a particular known function. If $R$ were analytic one could have used Darboux theorems to relate the answer to the type of nearest singularity. For a divergent non-Borel summable function I don't know whether there are general results. By the way, having the Borel transform in closed form could help because then one could deform the integration contour off the positive real axis to get information, in the spirit of Nevanlinna theorems.

Best Answer

TL;DR: I have a proof of your conjectured asymptotic formula, modulo the correctness of a certain alternative description of your $c_n$ sequence.


I tried to complete Iosif Pinelis's elegant analysis by finding a way to derive the value of the constant $2/\pi$ (denoted $a$ in Iosif's answer) from the quadratic recurrence relation. The problem with that relation is that the behavior it implies for $c_n$ for large $n$ seems to depend in a very sensitive way on the initial values of the sequence, so I concluded that this approach has little chance of working.

Fortunately, I've now discovered another, linear recurrence relation for the same sequence $c_n$ that has better behavior and gives your claimed asymptotics without much effort. The relation is:

$$ c_0=1, \qquad c_n = g_n + \sum_{k=1}^n h_k c_{n-k} \quad (n\ge 1), \qquad (*) $$ where I define \begin{align} g_n &= \frac{((2n)!)^2}{2^{3n}(n!)^3}, \\ h_n &= \frac{((2n)!)^2}{2^{3n}(n!)^3}\cdot \frac{2n-1}{2n+1}. \end{align} (Edit: this corrects a small typo from the earlier version. As you pointed out in a comment, $g_n$ can also be expressed as $\frac{2^n \Gamma(n+1/2)^2}{\pi \Gamma(n)}$.)

I haven't verified rigorously that this relation is equivalent to your quadratic relation, but numerically it gives the correct sequence 1, 2, 6, 24, 126, 864, 7596, ..., and I believe this should be straightforward to prove. The reasoning that led me to it involves your description of the sequence as coming from an asymptotic expansion for a ratio of two Bessel functions. I started with the relation $$ K_0(-1/4z) = K_1(-1/4z) \times \sum_{n} c_n z^n, $$ and, expanding both Bessel functions in a power series (actually not quite a traditional power series because of some nasty-looking transcendental terms, but those can be factored out), massaged this into a linear system of equations satisfied by the $c_n$'s, which gave me the recurrence after a bit of additional guesswork.

To rigorously prove the relation, one can work with this Bessel function picture and do the analysis more carefully, or one can try to prove directly that the linear recurrence is equivalent to the quadratic recurrence without any reference to Bessel functions. I suspect this is doable through an inductive argument, probably involving formulating and proving some auxiliary hypergeometric summation identities.

Finally, if we assume that $(*)$ is correct, we can prove your claim that $$ c_n \sim \frac{2}{\pi} 2^n (n-1)!. $$ Observe that $$ \frac{c_n}{2^n (n-1)!} = \frac{g_n}{2^n (n-1)!} + \frac{h_n}{2^n (n-1)!} + \frac{1}{2^n (n-1)!} \sum_{k=1}^{n-1} h_k c_{n-k} $$ Using Stirling's formula, you can check that each of the first two terms in this expression converges to $1/\pi$. The third term (the normalized sum) can be easily shown to be $O(1/n)$ (the first summand is $O(1/n)$, and the remaining summands are $O(1/n^2)$ and there are $n-2$ of them). Here I am using the fact that the sequence $c_n/2^n (n-1)!$ is bounded, as shown in Iosif Pinelis's answer (and as can probably also be shown from the linear recurrence without much effort).

Related Question