Estimate growth of a recurrence convolution

Question

Consider the following recurrence relation $$ a_{m+1} = (4 m + 1) \sum_{k=1}^m a_k a_{m-k+1}, \qquad a_1 = 1. $$ The first several values are $$ a_1 = 1,\; a_2 = 5,\; a_3 = 90, \; a_4 = 2665, \; a_5 = 105910. $$

I've taken first $3000$ terms of the sequence and it seems to me that $$ \lim_{k \to \infty} \frac{\log a_k}{k \log k} = 1, $$ but I don't know how prove that.

The best I could found were some theorems involving binomial coefficients, like $$ {2n \choose n} = \sum_{k=0}^{n} {n \choose k} {n \choose n-k}, $$ but I have no idea how to apply it here.

Also similar recurrence $$ b_{m+1} = \sum_{k=1}^{m} b_k b_{m-k+1}, \qquad b_1 = 1 $$ leads to Catalan numbers $$ b_m = \frac{1}{n+1} {2n \choose n} $$

Answer 1

Now because the sequence grows so quickly, it is easy to see that only the terms containing $a_m$ in the sum are going to be significant. Thus $a_{m+1} \approx (4m + 1) (a_m a_1 + a_1 a_m) \approx 8m a_m$. This tell us that $a_{m+1} \approx 8^m m!$. This initial guess can now be improved.

It is possible to prove by induction that there exists constants $\alpha$, $\beta$ and $M$ such that $\alpha 8^m (m-1)! < a_m < \beta 8^m (m+M)!$. From this it is easy to show $\log a_m$ ~ $m\log m$.

Answer 2

If we assume that $a_0=0$ and define $f(x)$ as: $$ f(x)=\sum_{n\geq 0} a_n x^{4n} \tag{1}$$ we have: $$ f(x)^2 = \sum_{n\geq 0}\left(\sum_{k=0}^{n} a_k a_{n-k}\right) x^{4n}\tag{2} $$ as well as: $$ x^4\cdot\frac{d}{dx}\left(\frac{f(x)^2}{x^3}\right) = \sum_{n\geq 0}(4n-3)\left(\sum_{k=0}^{n}a_k a_{n-k}\right)x^{4n} \tag{3}$$ and the recurrence relation turns out to be equivalent to a differential equation.
Can you write it down, solve it and get the asymptotic behaviour of your coefficients?
A better alternative is to work with an exponential generating function: $$ g(x)=\sum_{n\geq 0}\frac{a_n}{n!}x^{4n} \tag{4}$$ and to prove that the radius of convergence of the last power series at $x=0$ is just one.