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!

  • $\begingroup$ 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! $\endgroup$
    – nir shahar
    Jul 17, 2021 at 9:25
  • $\begingroup$ Thank you for up vote! $\endgroup$
    – ErroR
    Jul 17, 2021 at 9:32

2 Answers 2


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

  • $\begingroup$ More accurately, $\dfrac{T(n+1)}{T(n)}\sim 4$. $\endgroup$
    – John L.
    Mar 15, 2021 at 1:34
  • $\begingroup$ Thanks! It was surprising to know these are the catalan numbers! $\endgroup$
    – nir shahar
    Mar 15, 2021 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:


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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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