7
$\begingroup$

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.

$\endgroup$
6
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ @Aaron Lenz I edited my answer. $\endgroup$ – Robert Z Jul 26 at 7:44
  • $\begingroup$ Thank you very much! $\endgroup$ – Aaron Lenz Jul 26 at 12:10
  • $\begingroup$ 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.) $\endgroup$ – sasquires Jul 26 at 17:32
  • $\begingroup$ In case the identity above looks suspicious to you, note that for $j=0$ and $j=n$, the first factor is negative. $\endgroup$ – sasquires Jul 26 at 17:34
  • 1
    $\begingroup$ @AaronLenz Now you have two proofs! ;-) $\endgroup$ – Robert Z Jul 26 at 18:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.