Asymptotics of a quadratic recursion

Question

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.

Answer 1

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

Answer 2

Let us prove a bit less than conjectured in the OP: \begin{equation*} c_n\sim a(n-1)!2^n \tag{1}\label{1} \end{equation*} for some $a\in(0,1)$ (the conjectured value of $a$ was $2/\pi$).

Let \begin{equation*} a_n:=\frac{c_n}{(n-1)!2^n}. \tag{2}\label{2} \end{equation*} So, we have to show that $a_n\to a\in(0,1)$. We have \begin{equation*} a_1=1, \tag{3}\label{3} \end{equation*} \begin{equation*} \begin{aligned} a_n &= \frac n{n-1}\,a_{n-1}-\frac12\,\sum_{m=1}^{n-1}r_{n,m}a_m\,a_{n-m} \end{aligned} \tag{4}\label{4} \end{equation*} for $n\ge2$, where \begin{equation*} r_{n,m}:=\frac{(m - 1)! (n - m - 1)!}{(n - 1)!}. \tag{5}\label{5} \end{equation*} For any $n\ge3$ such that $a_1\ge0,\dots,a_{n-1}\ge0$, conditions \eqref{3}, \eqref{4}, and \eqref{5} imply \begin{equation*} a_n\le\frac n{n-1}\,a_{n-1}-\frac12\,(r_{n,1}a_1\,a_{n-1}+r_{n,n-1}a_{n-1}\,a_1)=a_{n-1}. \tag{7}\label{7} \end{equation*}

Note that
\begin{equation*} 3/2=a_2\ge\dots\ge a_{n-1}\ge a_n\ge\frac{11}n+\frac1{20} \tag{8}\label{8} \end{equation*} for $n=17$.

Let us show, by induction on $n$, that \eqref{8} holds for all natural $n\ge17$. Take indeed any natural $n\ge18$ and suppose that \eqref{8} holds with $n-1$ in place of $n$.

The condition $n\ge18$ implies $\frac{n-1}3-\log_2 n>1$ and hence there is a natural number $k$ such that \begin{equation*} \log_2 n\le k\le\frac{n-1}3. \tag{9}\label{9} \end{equation*} In what follows, we use such a $k$. Note that \begin{equation*} \rho_k\le1/2, \tag{10}\label{10} \end{equation*} where \begin{equation*} \rho_m:=\rho_{n,m}:=\frac{r_{n,m+1}}{r_{n,m}}=\frac{m}{n-m-1}. \tag{11}\label{11} \end{equation*} Note also that $\rho_m$ is increasing in $m\in[n-1]:=\{1,\dots,n-1\}$ and hence
\begin{equation*} r_{n,m}\le r_{n,2}\rho_k^{m-2}\le r_{n,2}(1/2)^{m-2}\text{ if }2\le m\le k, \tag{12}\label{12} \end{equation*} in view of \eqref{10}. Next, by \eqref{11}, $\rho_m\le1$ if $1\le m\le(n-1)/2$, so that
\begin{equation*} r_{n,m}\le r_{n,k}\le r_{n,2}(1/2)^{k-2} \text{ if }k\le m\le(n-1)/2, \tag{13}\label{13} \end{equation*} by \eqref{12}.

So, by \eqref{5}, \eqref{8} with $n-1$ in place of $n$, \eqref{12}, \eqref{13}, \eqref{9},
\begin{equation*} \begin{aligned} &\frac12\,\sum_{m=2}^{n-2}r_{n,m}a_m\,a_{n-m} \\ &=\sum_{2\le m\le(n-1)/2}r_{n,m}a_m\,a_{n-m} \\ &\le\Big(\frac32\Big)^2 \sum_{2\le m\le(n-1)/2}r_{n,m} \\ &=\frac94 \,\Big(\sum_{2\le m\le k}r_{n,m}+\sum_{k+1\le m\le(n-1)/2}r_{n,m} \Big) \\ &\le\frac94 \,\Big(\sum_{2\le m}r_{n,2}(1/2)^{m-2}+\frac n2\, r_{n,2}(1/2)^{k-2}\Big) \\ &\le\frac94 \,r_{n,2}(2+2)=\frac9{(n-1)(n-2)}. \end{aligned} \end{equation*} So, by \eqref{4} and \eqref{8} with $n-1$ in place of $n$, \begin{equation*} \begin{aligned} a_n&=a_{n-1}-\frac12\,\sum_{m=2}^{n-2}r_{n,m}a_m\,a_{n-m} \\ &\ge\frac{11}{n-1}+\frac1{20}-\frac9{(n-1)(n-2)} \\ &\ge\frac{11}n+\frac1{20}, \end{aligned} \end{equation*} since $n\ge18\ge11$. So, the last inequality in \eqref{8} holds; and the penultimate inequality in \eqref{8} holds by \eqref{7}.

This completes the proof of \eqref{8} for all $n\ge17$. Since $a_6<1$, we conclude that $a_n\to a$ for some $a\in[\frac1{20},1)\subset(0,1)$, as claimed.

Clearly, we can replace $\frac1{20}$ in \eqref{8} by any real number $<a=\lim_n a_n$, for the price of possibly having to replace $17$ by a greater number. Therefore and because $a_n\ge a$ for all $n\ge3$, we can bracket the limit $a$ with any degree of accuracy, if the amount of calculations is not a problem.