# A formal proof of how the following equation computes the nth catalan number?

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

• 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?
– πr8
Jan 12 '16 at 12:24
• How the recurrence relation can be obtained from the formula?
– user207526
Jan 12 '16 at 12:25
• 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$.
– πr8
Jan 12 '16 at 12:30

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}

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