Some recurrent formula for Catalan numbers 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?
 A: The most compact way to state this identity appears to be
$$\sum_{q=\lfloor (n+1)/2\rfloor}^{n+1}
(-1)^{q} {q+1\choose n+1-q} C_q = 0.$$
Note that with $q\le n+1$ a non-negative integer $(q+1)^\underline{n+1-q} = 0$
when $n+1-q > q+1$ or $n\gt 2q$ or $n\ge 2q+1.$ This is $\lfloor
(n-1)/2 \rfloor \ge q$ or $\lfloor (n+1)/2\rfloor \gt q.$ Hence we may
lower the starting index to zero:
$$\sum_{q=0}^{n+1} (-1)^{q} {q+1\choose n+1-q} C_q = 0.$$
This is
$$[z^{n+1}] \sum_{q=0}^{n+1} (-1)^{q} z^q (1+z)^{q+1} C_q $$
Here the coefficient extractor enforces the upper limit of the sum
and we get
$$[z^{n+1}] \sum_{q\ge 0} (-1)^{q} z^q (1+z)^{q+1} C_q
\\ = [z^{n+1}] \sum_{q\ge 0} (-1)^{q} z^q (1+z)^{q+1}
[w^q] \frac{1-\sqrt{1-4w}}{2w}
\\ = - [z^{n+1}] (1+z) \frac{1-\sqrt{1+4z(1+z)}}{2z(1+z)}
\\ = - [z^{n+1}]  \frac{1-\sqrt{(1+2z)^2}}{2z}
= - [z^{n+1}] (-1) = 0.$$
This is the claim.
A: 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}$.
