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.
$\begingroup$
$\endgroup$
3
-
1$\begingroup$ $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 ... $\endgroup$– darij grinbergDec 26, 2014 at 18:04
-
1$\begingroup$ ... $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). $\endgroup$– darij grinbergDec 26, 2014 at 18:05
-
$\begingroup$ For the record, this is known as Koshy's identity, see the references in mathoverflow.net/a/391985/11260 $\endgroup$– Carlo BeenakkerMay 6, 2021 at 6:57
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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$.