# Determining the asymptotic behavior of a sequence

I've encountered the following sequences

$$a_k=2^{k+1}\sum_{j=0}^{k-1}a_{k-1-j}a_j,\;a_0=1$$

$$b_k=(k+1)\sum_{j=0}^{k-1}b_{k-1-j}b_j,\;b_0=1.$$

I would like to have an estimate of the growth of these sequences as $k$ grows.

After looking here and there, I found the Catalan's numbers defined by $$C_k=\sum_{j=0}^{k-1}C_{k-1-j}C_j,\;C_0=1.$$ They have an asymptotic growth of $$C_k=2^{k+1}k^{-3/2}.$$

I tried (unsuccesfully) to manipulate my original series to recover some form of the Catalan's numbers.

Any idea is very welcome.

One type of Catalan's $q$-analogue is due to Carlitz (see the paper for this and more) $$C_{n+1}(q)=\sum_{k=0}^nC_k(q)\,C_{n-k}(q)\,q^{(k+1)(n-k)}, \qquad C_0:=1.$$ Blieberger and Kirschenhofer studied these Catalans, in equation (2), and the more related sequence $r_n$, in equation (5). They have found the asymptotics, on page 9, $$r_n\sim 2^{\frac{n^2+3n}2}\beta(1/2).$$ Now, your sequence is $a_n=2^nr_n$ and hence $$a_n\sim 2^{\frac{n^2+5n}2}\beta(1/2);$$ where $\beta(1/2)\approx 0.7153374336\dots$.

J. Furlinger and J. Hofbauer, $q$-Catalan Numbers, Jour. of Comb. Theory, Series A, 40(2):248–264, 1985.

J. Blieberger, P. Kirschenhofer, Generalized Catalan Sequences Originating from the Analysis of Special Data Structures, Bulletin of the Institute of Combinatorics and its Applications, 71 (2014), 103-116.

For $b_k$: Computing the first few terms and searching into https://oeis.org returns A218222 and A088716.

A088716 is very close to your sequence.

If $b_k$ is really A218222, from the comments:

$$b_n \sim C 2^{n-1} (n-1)! (n-1)^2$$

• Very similar to $a_k$ is oeis.org/A254744
– joro
May 23, 2017 at 15:14