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..
Best Answer
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.