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..
 A: The usual way to obtain a generating function from the Catalan number is to start with a different recurrence: $$C_n = C_{n-1} C_0 + C_{n-2} C_1 + \dots + C_1 C_{n-2} + C_0 C_{n-1},$$ valid when $n\ge 1$. (If $g(x)$ is the generating function for the sequence $(C_n)$, then the right-hand side is a coefficient of $g(x)^2$.)
The recurrence relation you've found is true but not very well-known, so I'm assuming the person who wrote the problem you're trying to solve didn't expect you to solve it this way. 
If you do intend to go on, you can rewrite the recurrence as $(n+2)C_{n+1} = (4n+2)C_n$ and use it to get a differential equation for $g(x)$, using the fact that $$g(x) = \sum_{n \ge 0} C_n x^n \implies g'(x) = \sum_{n \ge 0} n C_n x^{n-1}.$$ The differential equation I get by doing this is $(4x^2-x)g'(x) + (2x-1)g(x) + 1 = 0$, which (together with the initial condition $g(0)=1$) does indeed produce the generating function of the Catalan numbers.
A: 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*}

A: Going directly from your recursion is not to difficult, but first you need to correct the recursion -- your index is off by 1. The right relation is
$$
C_k = C_{k-1} \frac{4k+2}{k+2} + [k = 0]
$$
where $[k = 0]$ stands for a function of $k$ which is $1$ when $k=0$ and zero otherwise.
We define (for this derivation) $C_{n} = 0$ for all negative $n$.
Break up
$$ \frac{4k+2}{k+2} = 4 -  \frac{8k+8 -6}{k+2} =4-\frac{6}{k+2}$$
to get (R)
$$
C_k = 4 C_{k-1} -6 \frac{C_{k-1}}{k+2} + [k = 0]
$$
Multiply (R) by $z^k$ for all values of $k$ and sum those equations to get a generating function relation:
$$
\sum_{k=0}^\infty C_k z^k= 4 \sum_{k=0}^\infty C_{k-1}z^{k} -6\sum_{k=0}^\infty \frac{1}{k+2}C_{k-1}z^{k}+1
$$
Here, we have used the fact that $[k=0]$ contributes 1 to the sum when $k$ is zero, and nothing else.
Now shift the summation indices on the right by using $m=k-1$ so that only $C_d$ appears, where $d$ is a "dummy" (summed over) index, to get (S):
$$
C(z) \equiv \sum_{k=0}^\infty C_k z^k= 4 \sum_{m=0}^\infty C_{m}z^{m+1} -6\sum_{m=0}^\infty \frac{1}{m+1+2}C_{k-1}z^{m+1}+1
\\=4 z C(z) - 6\sum_{m=0}^\infty \frac{1}{m+3}C_{k-1}z^{m+1}+1
$$
The $(m+3)$ in the denominator would disappear if we had a $z^{m+3}$ multiplying it, and differentiated that term.  So multiply (S) by $z^2$ and differentiate with respect to $z$:
$$\frac{d}{dz} \left( z^2 C(z) \right) = 
4 \frac{d}{dz} \left( z^3 C(z) \right) + z^2 C(z) + \frac{d}{dz}(z^2)
$$
Use the multiplication rule for derivatives to simplify this and get (T):
$$
z^2 \frac{dC(z)}{dz} + 2z C(z) = 4z^3 \frac{dC(z)}{dz} +12 z^2 C(z) - 6 z^2 C(z) + 2 z\\
(4z^3-z^2)  \frac{dC(z)}{dz} + (6 z^2 -2 z) C(z)  + 2 z = 0
$$
Solve differential equation (T) to get
$$
C(z) = \frac{1-2z+\kappa \sqrt{1-4z}}{2z^2}
$$
The behavior of this function near $z=0$ is
$$
\frac{1+\kappa}{2z^2} - \frac{1+\kappa}{z} -\kappa + \cdots
$$
and since the coefficients for negative exponents of $z$ need to be zero, this determines that $\kappa = -1$.
$\kappa$ can be determined by noting that the constant term of the generating function must be $C_0 = 1$, and the which forces $\kappa = 1$. 
So the generating function for $C_k$ is
$$
C(z) = \frac{1-2z-\sqrt{1-4z}}{2z^2}
$$
