Some recurrent formula for Catalan numbers

Question

Recently, I noticed the following recurrent formula for Catalan numbers involving binomial coefficients:
$$
C_{n+1}
= \sum_{i=0}^n (-1)^{n+i}
\binom{i+1}{n+1-i} C_i.
$$
I have checked it for small values of n. This formula appears to be similar to the famous formula $C_{n+1}=\sum_{i=0}^{n}C_i C_{n-i}$. But I don't have an idea how to prove it. Can you help me please?

Answer 1

I find it helpful to rewrite the identity as

$$\begin{align*} C_{n+1}&=\sum_{k\ge 0}(-1)^k\binom{n+1-k}{k+1}C_{n-k}\tag{1}\\ &=(n+1)C_n-\binom{n}2C_{n-1}+\binom{n-1}3C_{n-2}-+\ldots\;; \end{align*}$$

No upper limit is needed on the summation, since the binomial coefficients are eventually $0$.

$C_n$ is the number of rooted binary trees with $n$ nodes; each of these has $n+1$ open slots at which a leaf can be added. Thus, to build one of the $C_{n+1}$ trees on $n+1$ nodes we can add a leaf in any one of $n+1$ places to any of the $C_n$ trees on $n$ nodes. This produces $(n+1)C_n$ trees on $n+1$ nodes, but some of them are duplicates.

For example, consider one of the $C_{n-1}$ trees on $n-1$ nodes. There are $\binom{n}2$ ways to pick two of the vacant slots at which a leaf can be added, and each such pair produces a tree on $n+1$ nodes in two ways, one for each of the two possible orders in which the two leaves can be added. Thus, the figure $(n+1)C_n$ overcounts by $\binom{n}2C_{n-1}$, and $(n+1)C_n-\binom{n}2C_{n-1}$ is a better estimate of $C_{n+1}$.

This analysis rapidly gets a bit awkward, however. Instead of trying to pursue it directly, let $T$ be a binary tree on $n+1$ nodes, and let $\ell$ be the number of leaves of $T$. $T$ is an extension of $\ell$ different $n$-trees (i.e., binary trees on $n$ nodes) by addition of a single leaf. It is an extension of $\binom\ell2$ different $(n-1)$-trees by the simultaneous addition of $2$ leaves. And in general for $k=1,\ldots,\ell$ it is the extension of $\binom\ell k$ different $(n+1-k)$-trees by the simultaneous addition of $k$ leaves.

For $k=0,\ldots,\ell-1$ let $\mathscr{T}_k$ be the set of $(n-k)$-trees of which $T$ is an extension by simultaneous addition of leaves, so that $|\mathscr{T}_k|=\binom\ell{k+1}$. Each member of $\mathscr{T}_0$ is counted once in $(n+1)C_n$, the $k=0$ term of $(1)$. Each member of $\mathscr{T}_1$ is counted once in $\binom{n}2C_{n-1}$, the absolute value of the $k=1$ term of $(1)$. And in general each member of $\mathscr{T}_k$ is counted once in $\binom{n+1-k}{k+1}C_{n-k}$. Thus, the summation in $(1)$ counts $T$

$$\sum_{k=0}^{\ell-1}(-1)^k\binom\ell{k+1}=\sum_{k=0}^{\ell}(-1)^{k+1}\binom\ell k-\left(-\binom\ell0\right)=0+1=1$$

time. This is the case for each binary tree on $n+1$ nodes, so the summation must indeed yield $C_{n+1}$.