# A recurrence relation on Catalan numbers

In the classical problem of bracketing $$n$$ numbers, I know the response is $$C_{n-1}$$. I find this $$C_{n-1}=\sum_{i=1}^{\left\lfloor\frac{n}{2}\right\rfloor}(-1)^{i+1}\binom{n-i}{i}C_{n-1-i}$$ but I can't prove that. Can someone help me? Regards.

• $C_{n-1}$ counts the triangulations of a given $\left(n+1\right)$-gon $N$. We say that a vertex $v$ of $N$ is an ear-vertex of a triangulation $T$ if no diagonal of $T$ contains $v$. Then, every triangulation has at least one ear-vertex (why?), and the ear-vertices of a given triangulation form a lacunar subset of the set of all vertices (where "lacunar" means that it contains no two adjacent vertices). For every nonnegative integer $i$, there are precisely $\binom{n-i}{i}$ lacunar subsets of the set of all vertices of $N$, and if $L$ is any such subset, then there exist precisely ... Dec 26 '14 at 18:04
• ... $C_{n-1-i}$ triangulations of $N$ for which all elements of $L$ are ear-vertices (but we allow other ear-vertices too) (because in effect we are triangulating an $\left(n+1-i\right)$-gon). Now the claim follows from inclusion-exclusion. I hope this proof is correct, as I have not checked my count of lacunar subsets... There is likely a clearer way to write up this proof using one of the less geometric interpretations of Catalan numbers (Dyck paths or trees). Dec 26 '14 at 18:05
• For the record, this is known as Koshy's identity, see the references in mathoverflow.net/a/391985/11260 May 6 at 6:57

Let $$C(x) = \sum_{n=1}^\infty C_{n-1} x^n = \frac{1-\sqrt{1-4x}}{2}.$$ Then the identity in question follows easily from $C(x(1-x)) = x$.