# Is there a good bound for this double exponential recursion?

Denote when $k>2m$ $$f_k(2m)=\sum_{i=1,i\geq1}^m\binom{2m}{i}f_k(i)f_k(2m-i)$$ $$f_k(2m+1)=\sum_{i=1,i\geq1}^m\binom{2m+1}{i}f_k(i)f_k(2m+1-i)$$

$$f_k(0)=1.$$ $$f_k(1)=k.$$

1. What is a good bound for $f_{2^{n+1}}(2^{n})$?

2. How does it compare with $\binom{2^{n+1}}{2^n}$? Is $f_{2^{n+1}}(2^{n})>\binom{2^{n+1}}{2^n}$?

• Your rules do not seem to work properly. They start with $f(0)=f(0)$, then $f(1)=f(0)f(1)$, then $f(2)=f(0)f(2)+2f(1)^2$, which does not determine $f(0)$, $f(1)$ and $f(2)$. Probably your equations should be adjusted slightly. – Neil Strickland Dec 18 '17 at 11:18
• What about $f(1)$? – Emil Jeřábek Dec 18 '17 at 11:49
• So now, $f(k,m)=k^mf(1,m)$, hence $f(2^{n+1},2^n)\ge2^{(n+1)2^n}\ge2^{2^{n+1}}>\binom{2^{n+1}}{2^n}$. – Emil Jeřábek Dec 18 '17 at 12:01
• Then do define it for $m>1$. The identity follows by trivial induction on $m$. – Emil Jeřábek Dec 18 '17 at 12:19
• I will try to expand in an answer – მამუკა ჯიბლაძე Dec 18 '17 at 12:46

## 1 Answer

For brevity, rewrite the recursion as$$f_k(n)=\sum_{1\leqslant i\leqslant\frac n2}\binom nif_k(i)f_k(n-i).$$Now divide it by $n!k^n$ and rewrite like this:$$\frac{f_k(n)}{n!k^n}=\frac1{n!}\sum_{1\leqslant i\leqslant\frac n2}\binom nii!(n-i)!\frac{f_k(i)}{i!k^i}\frac{f_k(n-i)}{(n-i)!k^{n-i}}.$$ It follows that for$$g_k(n):=\frac{f_k(n)}{n!k^n}$$we get$$g_k(n)=\sum_{1\leqslant i\leqslant\frac n2}g_k(i)g_k(n-i),$$and $g_k(1)=1$ (in particular $g_k(n)$ does not depend on $k$).

This is the recursion for A000992 (number of (unlabeled, rooted) ordered trees on $n-1$ vertices in which all outdegrees are $\leqslant2$ and, for each vertex of outdegree $2$, the sizes of its two subtrees are weakly increasing left to right ($n\geqslant2$)). That page contains some information about these numbers.

• So the growth of $g_k(n)$ is $\frac{1}{2(n+1)}\binom{2n}{n}$? – 1.. Dec 18 '17 at 13:00
• The fraction $\frac12$ comes from 'half-catalans' is 'catalan' by 2. – 1.. Dec 18 '17 at 13:00
• $\log(g(n))/\log(\textrm{Catalan}_n)$ seems to be unbounded – მამუკა ჯიბლაძე Dec 23 '17 at 9:12