$$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?
MathOverflow is a question and answer site for professional mathematicians. It only takes a minute to sign up.
Sign up to join this community$$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?
$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\}$.
Algebraically, this identity is $$\sum_{n=0}^\infty C(n) x^n (1-x)^{n+1} = 1, $$ which is a consequence of the generating function $$\sum_{n=0}^\infty C(n) x^n = \frac{1-\sqrt{1-4x}}{2x}.$$