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$ 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 at 9:25
  • $\begingroup$ Thank you for up vote! $\endgroup$ – Rostami.M Jul 17 at 9:32
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
2
$\begingroup$

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

$\endgroup$

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.