Showing asymptotic lower bound on log of recurrence

Question

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!

Answer 1

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

Answer 2

The lower bound of your recurrence is not $\Omega(n\log n)$, because:

1. We prove that the lower bound of your recurrence is $\Omega(2^n).$

Suppose $T(n)\geq c2^n$. Then:

$$ \sum_{k=1}^{n-1} T(k)T(n-k)\geq c2^n$$ $$=\sum_{k=1}^{n-1}\hspace{4pt} c2^kc2^{n-k}\geq c2^n$$ $$=\sum_{k=1}^{n-1}\hspace{4pt} c^22^n\geq c2^n$$ $$=\hspace{4pt} (n-1)c^22^n\geq c2^n.$$

So the lower bound of your recurrence $T(n)=\Omega(2^n).$ Consequently, $$\log T(n)=\Omega(n).$$

Because of your recurrence relation is $C_{n-1}$ nth Catalan number of Catalan numbers, then by reading this post we can find the exact solution of your recurrence is:

$$C_{n-1}=\frac{1}{n}\binom{2n-1}{n-1}$$

That $$C_{n-1}\leq 4^n$$ So $\log 4^n=\mathcal{O}(n).$