Simplifying Catalan number recurrence relation

Solution 1:

You can probably find it somewhere online, but for completeness here’s a derivation of the familiar closed form for $C_n$ from the recurrence $$C_n=\sum_{k=0}^{n-1}C_kC_{n-1-k}\tag{0}$$ and the initial value $C_0$, via the ordinary generating function. Then, as in Mhenni Benghorbal’s answer, you can easily (discover and) verify the first-order recurrence. I don’t see any nice way to get it directly from $(0)$.

Let the ordinary generating function for the Catalan numbers be

$$c(x)=\sum_{n\ge 0}C_nx^n=\sum_{n\ge 0}\sum_{k=0}^{n-1}C_kC_{n-1-k}x^n\;.$$

Then since $C_0=1$, we have

$$\begin{align*} c(x)&=\sum_{n\ge 0}\sum_{k=0}^{n-1}C_kC_{n-1-k}x^n\\ &=1+\sum_{n\ge 1}\sum_{k=0}^{n-1}C_kC_{n-1-k}x^n\\ &=1+x\sum_{n\ge 0}\sum_{k=0}^nC_kC_{n-k}x^n\\ &=1+x\left(\sum_{n\ge 0}C_nx^n\right)^2\\ &=1+xc(x)^2\;, \end{align*}$$

or $xc(x)^2-c(x)+1=0$. The quadratic formula then yields

$$c(x)=\frac{1\pm\sqrt{1-4x}}{2x}\;,\tag{1}$$

and since

$$\lim_{x\to 0}c(x)=\lim_{x\to 0}\sum_{n\ge 0}C_nx^n=C_0=1\;,$$

it’s clear that we must choose the negative square root in $(1)$, so that

$$c(x)=\frac{1-\sqrt{1-4x}}{2x}\;.$$

Now apply the binomial theorem to $\sqrt{1-4x}$:

$$\begin{align*} \left(1-4x\right)^{1/2}&=1+\sum_{n\ge 1}\binom{1/2}n(-4x)^n\\ &=1+\sum_{n\ge 1}\frac{\left(\frac12\right)\left(-\frac12\right)\left(-\frac32\right)\dots\left(-\frac{2n-3}2\right)}{n!}(-4x)^n\\ &=1+\sum_{n\ge 1}(-1)^{n-1}\frac{(2n-3)!!}{2^nn!}(-4x)^n\\ &=1-\sum_{n\ge 1}\frac{2^n(2n-3)!!}{n!}x^n\\ &=1-2\sum_{n\ge 1}\frac{2^{n-1}\prod_{k=1}^{n-1}(2k-1)}{n(n-1)!}x^n\\ &=1-2\sum_{n\ge 1}\frac{2^{n-1}(n-1)!\prod_{k=1}^{n-1}(2k-1)}{n(n-1)!^2}x^n\\ &=1-2\sum_{n\ge 1}\frac{\left(\prod_{k=1}^{n-1}(2k)\right)\left(\prod_{k=1}^{n-1}(2k-1)\right)}{n(n-1)!^2}x^n\\ &=1-2\sum_{n\ge 1}\frac{(2n-2)!}{n(n-1)!^2}x^n\\ &=1-2\sum_{n\ge 1}\frac1n\binom{2(n-1)}{n-1}x^n\;, \end{align*}$$

so

$$\begin{align*} c(x)&=\frac1{2x}\cdot2\sum_{n\ge 1}\frac1{n}\binom{2(n-1)}{n-1}x^n\\ &=\sum_{n\ge 1}\frac1n\binom{2(n-1)}{n-1}x^{n-1}\\ &=\sum_{n\ge 0}\frac1{n+1}\binom{2n}nx^n\;, \end{align*}$$

and we have the familiar closed form $C_n=\dfrac1{n+1}\dbinom{2n}n$.

Solution 2:

A related problem. It is easier to prove it using the identity

$$ C_n = \frac{1}{n+1}{2n\choose n} = \frac{(2n)!}{(n+1)!\,n!} \implies C_{n-1}=\frac{(2(n-1))!}{(n)!\,(n-1)!} $$

$$ \frac{C_n}{C_{n-1}}= \frac{ (2n)(2n-1)(2n-2)!(n-1)! }{(n+1)n(n-1)!(2n-2)!}=\frac{2(2n-1)}{n+1} $$

$$ \implies C_n = \frac{2(2n-1)}{n+1} C_{n-1}. $$

Added: We will find the ordinary generating function. Let $g(x)=\sum_{n=0}^{\infty}C_{n}x^{n} $

$$ C_{n+1} = \displaystyle\sum_{i=0}^{n } C_{i}C_{n - i } \implies \sum_{n=0}^{\infty}C_{n+1}x^n = \sum_{n=0}^{\infty} \sum_{i=0}^{n } C_{i}C_{n - i } x^n $$

$$ \implies \sum_{n=1}^{\infty}C_{n}x^{n-1} = \sum_{i=0}^{\infty}C_i\sum_{n=i}^{\infty}C_{n-i}x^n= \sum_{i=0}^{\infty}C_i\sum_{n=0}^{\infty}C_{n}x^{n+i}$$

$$\implies \frac{1}{x}\sum_{n=0}^{\infty}C_{n}x^{n}-\frac{C_0}{x}= \sum_{i=0}^{\infty}C_ix^i\sum_{n=0}^{\infty}C_{n}x^{n} $$

$$ \implies \frac{g(x)}{x}-\frac{1}{x} = g(x)g(x) = g(x)^2 $$

$$ \implies g(x)^2-\frac{g(x)}{x}+\frac{1}{x} = 0. $$

Solution 3:

Note: This answer is merely a slight variation of the answers already given. The derivation of the generating function of the Catalan Numbers is somewhat different which may be convenient for the reader.

The following is valid: The recurrence relation \begin{align*} C_{0} = 1, C_{n} = \displaystyle\sum_{i=0}^{n - 1} C_{i}C_{n - i - 1}\qquad(n\geq 1)\tag{1} \end{align*} specifies the Catalan Numbers \begin{align*} \qquad\qquad\frac{1}{n+1}\binom{2n}{n}\qquad\qquad(n\geq 0)\tag{2} \end{align*}

Note: The connection between the closed formula (2) and the formula stated in the question is given at the beginning of the answer from @MhenniBenghorbal.

Generating function for $C_n$:

When looking at the recurrence relation we see that $\sum_{i=0}^{n - 1} C_{i}C_{n - i - 1}$ is a Cauchy-Product. Since Cauchy products occur when multiplying series it seems natural to work with the following generating functions:

\begin{align*} C(z) = \sum_{n\geq 0}C_nz^n\qquad\text{and}\qquad C^2(z)=\sum_{n\geq 0}\left(\sum_{i=0}^{n}C_iC_{n-i}\right)z^n\tag{3} \end{align*}

Let $[z^n]$ denote the coefficient operator. We observe with the help of (1) and (3):

\begin{align*} [z^n]C(z)&=C_n\\ &=\sum_{i=0}^{n-1}C_iC_{(n-1)-i}\\ &=[z^{n-1}]C^2(z)\\ &=[z^n]zC^2(z)\qquad\qquad\qquad(n\geq 1)\\ \\ [z^0]C(z)&=C_0=1\\ \end{align*}

Therefore we get

\begin{align*} C(z)=zC^2(z)+C_0=zC^2(z)+1 \end{align*}

and solving the quadratic equation gives

\begin{align*} C_{1,2}(z)=\frac{1}{2z}\left(1\pm\sqrt{1-4z}\right) \end{align*} Since the expansion of $\sqrt{1-4z}=1-2z-\ldots$ and $C(z)= \sum_{n\geq 0}C_nz^n$ is a power series in $z$ we conclude that following solution is valid:

\begin{align*} C(z)=\frac{1}{2z}\left(1-\sqrt{1-4z}\right) \end{align*}

Now:

Calculation of $C_n$:

With the help of the well known binomial identity $$\binom{\frac{1}{2}}{n}=\frac{(-1)^{n+1}}{4^n(2n-1)}\binom{2n}{n}$$ we get \begin{align*} C_n&=[z^n]\frac{1}{2z}\left(1-\sqrt{1-4z}\right)\\ &=-\frac{1}{2}[z^{n+1}]\sqrt{1-4z}\\ &=-\frac{1}{2}[z^{n+1}]\sum_{n\geq 0}\binom{\frac{1}{2}}{n}\left(-4z\right)^n\\ &=-\frac{1}{2}\binom{\frac{1}{2}}{n+1}\left(-4\right)^{n+1}\\ &=\frac{1}{2}\frac{1}{2n+1}\binom{2n+2}{n+1}\\ &=\frac{1}{2}\frac{1}{2n+1}\frac{(2n+2)(2n+1)}{(n+1)^2}\binom{2n}{n}\\ &=\frac{1}{n+1}\binom{2n}{n} \end{align*}