Catalan numbers - algebraic proof of the recurrence relation

Question

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.

Answer 1

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.