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