Finding a closed formula for a generating function involving catalan numbers

Question

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

Answer 1

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.

Answer 2

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*}