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

  • 3
    $\begingroup$ Obvious comment: looks like some kind of inclusion-exclusion... $\endgroup$ May 6 at 20:26
  • 14
    $\begingroup$ I rolled back your edit; you asked for a proof and received a proof; please don't change the question afterwards. $\endgroup$ May 6 at 21:09
  • 3
    $\begingroup$ This is not research level. It is more appropriate for math.stackexchange.com. $\endgroup$
    – PatrickR
    May 8 at 19:18

2 Answers 2


$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\}$.

  • 1
    $\begingroup$ Could you explain why there are nCr (𝑛−𝑖+1, i) number of ways to choose 𝑖 special pairs? $\endgroup$
    – banana
    May 6 at 23:59
  • 2
    $\begingroup$ @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. $\endgroup$
    – Alapan Das
    May 7 at 4:49
  • 4
    $\begingroup$ 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$ $\endgroup$ May 7 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}.$$


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .