# Catalan numbers - algebraic proof of the recurrence relation

I would like to prove following recursive relation for the Catalan numbers: $$\tag{1} C_0=1,\quad C_n=\sum_{i=0}^{n-1}C_iC_{n-i-1}\text{, for }n\ge 1$$ without combinatoric arguments, only algebraically; and no generating function.

Starting point: $$\tag{2} C_n:=\frac{1}{n+1}\binom{2n}{n}.$$ The following recursion can be also used (already proved): $$\tag{3} C_0=1,\quad C_n=\frac{2(2n-1)}{n+1}C_{n-1}\text{, for }n\ge 1$$ Maybe the identities for Binomial coefficients (wikipedia) are useful. In particular the Chu–Vandermonde identity, $$\tag{4a} \sum _{j=0}^{k}{\binom {m}{j}}{\binom {n-m}{k-j}}={\binom {n}{k}}$$ or $$\tag{4b} \sum _{m=0}^{n}{\binom {m}{j}}{\binom {n-m}{k-j}}={\binom {n+1}{k+1}}$$ could be useful.

What I have tried? I tried to substitute the definition (2) in the r.h.s. of (1) to obtain the l.h.s. of (1). Another attempt was to take $$C_{n-1}$$ from (1) (known by induction assumption) and try with (3) to recover $$C_n$$. In both cases, although I can smell that every thing is more or less related I can't find the technical steps to do the job.

A combinatoric proof with Dyck paths can be found here, but this is not the way I'm trying to follow.

EDIT The answer by "Robert Z" is very good and nice and I'll accept it; if someone could find a direct proof without generalised binomial coefficient, I'will accept his answer instead.

First proof.

Note that for $$0\leq i\leq n-1$$, $$C_iC_{n-i-1}=a(n,i+1)-a(n,i)$$ where $$a(n,j):=\frac{(2j-n)}{2n(n+1)}\binom{2j}{j}\binom{2(n-j)}{n-j}.$$ Hence, for $$n\geq 1$$, \begin{align}\sum_{i=0}^{n-1}C_iC_{n-i-1}&= \sum_{i=0}^{n-1}(a(n,i+1)-a(n,i))\\&=a(n,n)-a(n,0)=C_n. \end{align}

Second proof.

We have that $$C_n=\frac{2(2n-1)\cdots (n+1)n}{(n+1)!}=2(-4)^n\binom{1/2}{n+1}$$ where we use the notion of generalized binomial coefficient.

Hence, for $$n\geq 1$$, \begin{align}\sum_{i=0}^{n-1}C_iC_{n-i-1}&=4\sum_{i=0}^{n-1}(-4)^i\binom{1/2}{i+1}(-4)^{n-i-1}\binom{1/2}{n-i}\\ &=-(-4)^n\sum_{j=1}^{n}\binom{1/2}{j}\binom{1/2}{n+1-j}\\ &=-(-4)^n\sum_{j=0}^{n+1}\binom{1/2}{j}\binom{1/2}{n+1-j}+2(-4)^{n}\binom{1/2}{n+1}\\ &=0+C_n=C_n\end{align} where we applied the generalized Chu–Vandermonde identity.

• @Aaron Lenz I edited my answer. Commented Jul 26, 2019 at 7:44
• Thank you very much! Commented Jul 26, 2019 at 12:10
• The central step here is $\sum_{j=0}^n \binom{1/2}{j} \binom{1/2}{n-j} = 0$. If you translate quantities of the form $\binom{1/2}{n}$ back into central binomial coefficients, then this becomes the identity $$\sum_{j=0}^n \frac{1}{(2j-1)(2n-2j-1)} \binom{2j}{j} \binom{2n-2j}{n-j} = 0$$ So if we want to make this proof meet the OP's request to avoid generalized binomial coefficients, then we probably need to find a proof for this identity about central binomial coefficients. (It is closely related to the Catalan recurrence relation, but looks slightly simpler and may be easier to prove.) Commented Jul 26, 2019 at 17:32
• @AaronLenz Now you have two proofs! ;-) Commented Jul 26, 2019 at 18:51
• @Sarvagya In general use Gosper's algorithm. See www2.math.upenn.edu/~wilf/gfology2.pdf Commented Apr 6, 2021 at 14:47