I would like to know if the following recurrence relation for Catalan numbers (see [mathoverflow.net/questions/191524](https://mathoverflow.net/questions/191524/a-recurrence-relation-on-catalan-numbers) and also [math.stackexchange.com/questions/2113830](https://math.stackexchange.com/questions/2113830/recurrence-relation-for-catalan-numbers)) has appeared in a paper or a book, so that I can cite it.


$$C\_n = 1 + \sum\_{k=1}^{\left\lceil\frac{n}{2} \right\rceil
} (-1)^{k+1} \binom{n-k}{k} C\_{n-k}$$
where $C\_n$ is the $n$-th Catalan number.


Fixed error: added + 1 to the right hand side



Reference request: recurrence relation for Catalan numbers
T. Koshy, *Catalan Numbers with Applications* (Oxford, 2009), [page 322](https://books.google.com/books?id=o50RDAAAQBAJ&pg=PA322), proves a very similar identity:
$$C\_n=\sum\_{k=1}^{\left\lfloor\frac{n+1}{2}\right\rfloor}(-1)^{k-1} \binom{n-k+1}{k} C\_{n-k}$$
$$\Leftrightarrow \sum\_{k=1}^{\left\lfloor\frac{n+1}{2}\right\rfloor} (-1)^{k-1} \binom{n-k+1}{k} C\_{n-k}=0.$$
(I did not check the book, the identity is quoted in this [paper,](https://www.mdpi.com/2227-7390/4/2/35) equation 4.)


I also note that Mathematica knows the identity in the OP, in the form


$$\sum\_{k=0}^{\left\lceil\frac{n}{2} \right\rceil
} (-1)^{k+1} \binom{n-k}{k} C\_{n-k}=-1,$$
(Floor or ceiling in the summation limits does not matter, the sum may also be extended to infinity, since the binomial coefficients vanish.)




---


In response to a question in the comment, I record the q-analog of Koshy's identity, derived by [George Andrews.](http://www.personal.psu.edu/gea1/pdf/275.pdf)


![](https://i.stack.imgur.com/ojfTG.png)
(The sum over $r$ may be terminated at $\left\lfloor\frac{n+1}{2}\right\rfloor$.)


