**Question**. Do these identities involving even-index Catalan numbers have a known combinatorial interpretation? They look as though they should. I haven’t seen one in the literature.


$$\sum\_{a+b=n}C\_{2a}C\_{2b}=4^nC\_n$$


$$\sum\_{a+b=n}C\_{2a}{4b\choose 2b}=4^n{2n\choose n}$$




---


**Added**. Thanks to Richard Stanley’s helpful answer, I now know that the first of these identities is known in the literature as *Shapiro’s Catalan convolution*, and has [a bijective proof due to Hajnal and Nagy (2014)](http://www.combinatorics.org/ojs/index.php/eljc/article/viewFile/v21i2p42/pdf).


**Added further**. I hadn’t realised *quite* how straightforwardly each of these identities implies the other. For example, if the first holds then: $$\begin{align}
2\sum\_{a+b=n}C\_{2a}{4b\choose 2b}&=2\sum\_{a+b=n}(2b+1)C\_{2a}C\_{2b}\\
&=\Bigl(\sum\_{a+b=n}(2a+1)C\_{2a}C\_{2b}\Bigr)+\Bigl(\sum\_{a+b=n}(2b+1)C\_{2a}C\_{2b}\Bigr)\\
&=(2n+2)\sum\_{a+b=n}C\_{2a}C\_{2b}\\
&=(2n+2)4^nC\_n\\
&=2\cdot 4^n {2n\choose n}
\end{align}$$
In light of that, a proof of one is essentially also a proof of the other.




---


**Notes**.
I came across these identities while thinking about [an unanswered question of Mike Spivey from 2012](/questions/86924/combinatorial-proof-for-the-number-of-lattice-paths-that-return-to-the-axis-only?rq=1). I can define a bijection for the first one – I imagine the second can be done in a similar way – but it isn’t obviously a very *nice* bijection, and it uses Garsia-Milne involution. Here is a description of it, in the language of species.


If $D$ is the species of Dyck paths with matching up/down pairs labelled (or binary plane trees with internal nodes labelled, etc.) then $D=1+XD^2$, where $1$ is the species of the empty set (sometimes denoted $E\_0$) and $X$ is the species of singletons ($E\_1$). Split $D=D'+D''$, where $D'$ represents paths of odd semilength and $D''$ even, so we have the mutually recursive isomorphisms $$\begin{align}\tag{1}D''&=1+2XD'D''\\\tag{2}D'&=X(D'^2 + D''^2)\end{align}$$ (using the $=$ sign to denote isomorphism). The aim is to define an isomorphism between $D''^2$ and $1 + 4X^2D''^4$. We shall do this by defining an isomorphism $$D''^2+Y=1 + 4X^2D''^4+Y$$ for the species $Y=(2XD'D'')^2$, and appealing to the Garsia-Milne principle. Here is the isomorphism, from right to left:


$$\begin{align}
1 + 4X^2D''^4+Y&=1 + 4X^2D''^2(D'^2+D''^2)\\
&=1 + 4XD'D''^2\tag{using 2}\\
&=1 + 4XD'D''(1+2XD'D'')\tag{using 1}\\
&=1 + 4XD'D'' + 8(XD'D'')^2\\
&=D''^2 + 4(XD'D'')^2\tag{using 1}\\
&=D''^2 + Y
\end{align}$$



Curious Catalan convolutions
For the first identity, see additional problem A33 in my book *Catalan Numbers*. References are given to bijective proofs by Andrews and Nagy.


