# Reference request: recurrence relation for Catalan numbers

I would like to know if the following recurrence relation for Catalan numbers (see mathoverflow.net/questions/191524 and also math.stackexchange.com/questions/2113830) 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

• This will certainly appear in one of the two volumes of Stanley's "Enumerative Combinatorics", which have enormous lists of facts about Catalan numbers. But my copies are in my office, which I have not visited for a year. May 5, 2021 at 15:24
• I looked around in EC a bit and couldn’t find it. The proof given by Ira Gessel is very immediate so I’m not sure a reference is really required... May 5, 2021 at 15:30
• Stanley has been known to answer questions here on occasion: mathoverflow.net/users/2807/richard-stanley May 5, 2021 at 18:23
• Have you checked doi.org/10.1017/CBO9781139871495? May 6, 2021 at 21:04
• @LuisFerroni: that book also does not contain so much by way of identities satisfied by Catalan numbers; rather it focuses on combinatorial (and algebraic, geometric, etc.) interpretations of Catalan numbers. May 7, 2021 at 19:21

T. Koshy, Catalan Numbers with Applications (Oxford, 2009), page 322, 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, 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. (The sum over $$r$$ may be terminated at $$\left\lfloor\frac{n+1}{2}\right\rfloor$$.)

• In fact the first identity you write is the one from the linked MO question: mathoverflow.net/questions/191524/… (see $n$ vs. $n-1$). May 5, 2021 at 16:38
• And probably the 2nd identity is what you get from subtracting the 1st identity for $n$ from the 1st identity for $n-1$, or something like that. May 5, 2021 at 16:41
• Is there a q-analog of this identity? May 5, 2021 at 22:02
• @PerAlexandersson --- yes there is, I added it. May 6, 2021 at 6:23
• @CarloBeenakker Ah, that's great! I tried a bit to find it by experimentation, but that last factor is not super obvious. May 6, 2021 at 7:37