# Proving an identity about Catalan numbers

$$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?

• Obvious comment: looks like some kind of inclusion-exclusion... Commented May 6, 2023 at 20:26
• I rolled back your edit; you asked for a proof and received a proof; please don't change the question afterwards. Commented May 6, 2023 at 21:09
• This is not research level. It is more appropriate for math.stackexchange.com. Commented May 8, 2023 at 19:18
• I have a generalized version of this identity for the classic Fuss-Catalan numbers at my mini-arXiv ; "A Catalan Identity Related to Fibonacci Polynomials and Its Generalization to the Fuss-Catalan Number Sequences". It notes an article by Doslic that contains a combinatorial proof for a more general identity that encompasses this Catalan identity. (tcjpn.wordpress.com/2023/05/31/…). This replaces my May 12 answer. Commented Jun 2, 2023 at 21:15

$$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\}$$.
• @banana Consider the $i$ pairs $j,j+1$ as $i$ boxes (which may includes $n+1$ as well). Now put the remaining $n-2i+1$ numbers can be arranged in $i+1$ ( the places in between the boxes and on the sides) in $\binom{n-i+1}{i}$ ways. Commented May 7, 2023 at 4:49
• if $j_1<j_2<\ldots<j_i$ are first elements of $i$ special pairs, then $j_1<j_2-1<j_3-2<\ldots <j_i-i+1\leqslant n-i+1$ are distinct numbers between 1 and $n-i+1$ Commented May 7, 2023 at 6:17
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}.$$