Finding a closed formula for a generating function involving catalan numbers For $n$ $\ge$ $1$, let the Catalan number $C_n$ be defined to be the number of ways of partitioning a convex $(n+2)$-gon into $n$ triangles by using diagonals that do not cross one another (except perhaps at their ends). By convention set $C_0$ $=$ $1$. 
Find a recurrence relation expressing $C_n$ in terms of the Catalan numbers of smaller index.
I have found this to be $C_{n+1}$ $=$ $\frac{4n+2}{n+2}C_n.$
I want to use this to find a closed formula for the generating function $$g(x) = \sum_0^{\infty}C_nx^n.$$
Please help me..

Here is another two-step approach to derive the generating function of the Catalan numbers from the recurrence relation
\begin{align*}
C_{n+1}&=\frac{4n+2}{n+2}C_n\qquad\qquad n\geq 0\tag{1}\\
C_0&=1
\end{align*}

First step: $C_n$
We can iteratively apply the recurrence relation (1) and obtain
  \begin{align*}
C_n&=\frac{4n-2}{n+1}\cdot C_{n-1}\\
&=\frac{4n-2}{n+1}\cdot\frac{4n-6}{n}\cdot C_{n-2}\\
&=\frac{4n-2}{n+1}\cdot\frac{4n-6}{n}\cdots\frac{2}{1}\cdot C_0\\
&=\frac{2^n}{(n+1)!}\cdot (2n-1)(2n-3)\cdots 3\cdot 1\tag{2}\\
&=\frac{2^n(2n-1)!!}{(n+1)!}\tag{3}\\
&=\frac{2^n}{(n+1)!}\cdot\frac{(2n)!}{2^nn!}\tag{4}\\
&=\frac{1}{n+1}\binom{2n}{n}
\end{align*}

Comment:


*

*In (2) we factor out $2^n$ and use $C_0=1$.

*In (3) we use the double factorial as compact notation.
\begin{align*}
(2n)!!&=2n\cdot(2n-2)\cdots 4\cdot 2\\
(2n-1)!!&=(2n-1)\cdot(2n-3)\cdots 3\cdot 1\\
\end{align*}

*In (4) we use
\begin{align*}
(2n)!=(2n)!!(2n-1)!!\qquad\text{and}\qquad (2n)!!=2^nn!
\end{align*}

Second step: $g(x)= \sum_{n=0}^{\infty}C_nx^n$
We use the binomial identity 
  \begin{align*}
\binom{2n}{n}=(-4)^n\binom{-\frac{1}{2}}{n}
\end{align*}
  (see e.g. formula (1.9) in H.W. Goulds Combinatorial Identities, vol. I) and obtain
  \begin{align*}
C_n&=\frac{1}{n+1}\binom{2n}{n}=\frac{(-4)^n}{n+1}\binom{-\frac{1}{2}}{n}
=2(-4)^{n}\binom{\frac{1}{2}}{n+1}\\
&=-\frac{1}{2}(-4)^{n+1}\binom{\frac{1}{2}}{n+1}\tag{5}
\end{align*}
  With the representation of $C_n$ stated in  (5) we are well prepared to derive the generating function $g(x)$ by a binomial series expansion.
We obtain
  \begin{align*}
\sum_{n=0}^\infty C_nx^n&=\sum_{n=0}^\infty-\frac{1}{2}(-4)^{n+1}\binom{\frac{1}{2}}{n+1}x^n\\
&=-\frac{1}{2x}\sum_{n=0}^\infty\binom{\frac{1}{2}}{n+1}(-4x)^{n+1}\\
&=-\frac{1}{2x}\sum_{n=1}^\infty\binom{\frac{1}{2}}{n}(-4x)^{n}\\
&=-\frac{1}{2x}\left((1-4x)^{\frac{1}{2}}-1\right)\\
&=\frac{1}{2x}\left(1-\sqrt{1-4x}\right)
\end{align*}

