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!

• Hi, thanks for the answer! I have already seen it and upvoted, however I can't accept your asnwer as I have alteady accepted a different useful asnwer a few months ago. Thanks for adding your solution as well! Jul 17 at 9:25
• Thank you for up vote!
– Jut
Jul 17 at 9:32

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$. Mar 15 at 1:34
• Thanks! It was surprising to know these are the catalan numbers! Mar 15 at 8:46

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