Simplifying Catalan number recurrence relation

Question

While solving a problem, I reduced it in the form of the following recurrence relation.

$ C_{0} = 1, C_{n} = \displaystyle\sum_{i=0}^{n - 1} C_{i}C_{n - i - 1} $

However https://en.wikipedia.org/wiki/Catalan_number tells me, this is the recurrence relation for catalan numbers and it can be further simplified as,

$ C_{0} = 1, C_{n} = \displaystyle\frac {2(2n - 1)}{n + 1} C_{n - 1}$

How can I derive the second relationship from the first one ? One way is to prove it is by induction, but we don't know the simplified recurrence so far.

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

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