2
$\begingroup$

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!

$\endgroup$
2
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ More accurately, $\dfrac{T(n+1)}{T(n)}\sim 4$. $\endgroup$ – John L. Mar 15 at 1:34
  • $\begingroup$ Thanks! It was surprising to know these are the catalan numbers! $\endgroup$ – nir shahar Mar 15 at 8:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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