0
$\begingroup$

$t(0)=1$
$t(n+1)=\sum_{i=0}^n t(i)*t(n-i)$ $ ,n>=0$

nth Catalan number is given by :-
$t(n)=2nCn/(n+1) $

I tried breaking the latter formula into a Summation of pairs, but it did not work.

My question is how the recurrence relation can be obtained from nth Catalan number relation or if we can someone see the solution intuitively?

$\endgroup$
3
  • $\begingroup$ Just to clarify, are you asking for a proof of how the sequence $t(n)=\frac{2n\choose n}{n+1}$ solves the given recurrence? $\endgroup$
    – πr8
    Jan 12 '16 at 12:24
  • $\begingroup$ How the recurrence relation can be obtained from the formula? $\endgroup$
    – user207526
    Jan 12 '16 at 12:25
  • 2
    $\begingroup$ Hm, okay. Maybe worth noting that (at least in my experience), it's more common to start with the recurrence to obtain the explicit formula. In any case, I've most often seen the equivalence proven via generating functions, i.e. setting up the function $C(x):=\sum_n t(n)x^n$ and showing that it satisfies $C(x)=1+xC(x)^2$. $\endgroup$
    – πr8
    Jan 12 '16 at 12:30
1
$\begingroup$

Use generating functions.

Define $C(z) = \sum_{n \ge 0} t(n) z^n$, multiply your recurrence by $z^n$ and add over $n \ge 0$. Recognize the resulting sums:

$\begin{align} \sum_{n \ge 0} t(n + 1) z^n &= \sum_{n \ge 0} \sum_{0 \le i \le n} t(i) t(n - i) z^n \\ \frac{C(z) - t(0)}{z} &= C^2(z) \end{align}$

This gives the quadratic:

$\begin{align} z C^2(z) - C(z) + 1 = 0 \end{align}$

Solutions to this are:

$\begin{align} C(z) = \frac{1 \pm \sqrt{1 - 4 z}}{2 z} \end{align}$

We know $t(0) = 1$, so it should be that $\lim_{z \to 0} C(z) = 1$, and the right sign is negative.

Expanding the root as a series by the generalized binomial theorem we get:

$\begin{align} \sqrt{1 - 4 z} &= \sum_{n \ge 0} (-1)^n \binom{1/2}{n} \cdot 4^n z^n \\ &= 1 + \sum_{n \ge 1} (-1)^n \cdot \frac{(-1)^{n - 1}}{2^{2 n - 1} n} \binom{2 n - 2}{n - 1} \cdot 4^n z^n \\ &= 1 - \sum_{n \ge 1} \frac{2}{n} \binom{2 n - 2}{n - 1} z^n \end{align}$

Replacing in the expression for $C(z)$:

$\begin{align} C(z) &= \frac{1 - \left( 1 - \sum_{n \ge 1} \frac{2}{n} \binom{2 n - 2}{n - 1} z^n \right)}{2 z} \\ &= \sum_{n \ge 1} \frac{1}{n} \binom{2 n - 2}{n - 1} z^{n - 1} \\ &= \sum_{n \ge 0} \frac{1}{n + 1} \binom{2 n}{n} z^n \end{align}$

Thus $t(n) = \frac{1}{n + 1} \binom{2 n}{n}$, as claimed.

$\endgroup$
0

Your Answer

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