$$C\_{n} = \sum\_{i=1}^n (-1)^{i-1} \binom{n-i+1}{i} C\_{n-i}$$


Are there any good combinatorial proofs or algebraic proofs of this?



Proving an identity about Catalan numbers
$C\_n$ is the number of *Catalan sequences* $(x\_1,\ldots,x\_{2n})$ of $\pm 1$ with zero sum and non-negative prefix sums $x\_1+\ldots+x\_k$, for $k=1,\ldots,2n$. Note that any such sequence contains an index $j\in \{1,2,\ldots,n\}$ for which $x\_j=1$, $x\_{j+1}=-1$. Call $(j,j+1)$ a special pair. Then ${n-i+1\choose i}$ is the number of ways to choose $i$ special pairs (they are of course disjoint), and $C\_{n-i}$ is the number of Catalan sequences with these $i$ pairs being special. Then your identity is just inclusion-exclusion. Note that the same argument shows that $$C\_n=\sum\_i (-1)^{i-1}{n+1+t-i\choose i}C\_{n-i}$$
for every $t=0,1,\ldots,n-1$, if we consider special pairs with $j\in \{1,2,\ldots,n+t\}$.


