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$$

  • 1
    $\begingroup$ Very similar to $a_k$ is oeis.org/A254744 $\endgroup$ – joro May 23 '17 at 15:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.