# Showing asymptotic lower bound on log of recurrence

I'm trying to prove a lower bound on some computational problem, but in order to do it, I need an $$\Omega(n\log(n))$$ lower bound on $$\log(T(n))$$, where $$T(n)$$ is a recurrence defined as follows:

$$T(1) = 1$$

$$T(n) = \sum_{k=1}^{n-1} T(k)T(n-k)$$

Does this recurrence have a known solution? If not, just giving a lower bound on $$\log(T(n))$$ would suffice for me. Optimally, I would want an $$n\log(n)$$ bound, but I don't know if its possible to achieve. So, any lower bound bigger than a linear one would be appreciated! Thanks in advance for helping me out!

Your sequence $$T(n)$$ is, in fact, the Catalan numbers, as show on the On-Line Encyclopedia of Integer Sequences. You can also take a look at the Wikipedia article on Catalan numbers, which shows its many applications in combinatorics.
$$T(n)=C(n-1)=\frac{(2(n-1))!}{n!(n-1)!}\sim \frac{4^{n-1}}{n^{3/2}\sqrt{\pi}}.$$
In particular, $$\log T(n) = (n-1)\log 4 - \frac32\log n - \frac12\log\pi + o(1),$$ or,$$\log T(n) \sim n\log 4.$$
• More accurately, $\dfrac{T(n+1)}{T(n)}\sim 4$. – John L. Mar 15 at 1:34