Skip to main content
1 of 6

A bijective proof to the odd companion of Shapiro's Catalan convolution

Shapiro's Catalan convolution is the following formula (where $C_n$ is the $n$th Catalan number): $$ \sum_{k=0}^{n}{C_{2k}C_{2(n-k)}}=4^nC_n. $$ In other words, letting $C(z)=\sum_{n=0}^{\infty}{C_nz^n}$, and $C_\mathrm{even}(z^2)=\dfrac{C(z)+C(-z)}{2}$, we have $(C_\mathrm{even}(z))^2=C(4z)$. See, for example, Curious Catalan convolutions and Proofs of some combinatorial identities for further discussion of this and links to bijective proofs of this identity.

I am wondering a similar bijective proof exists in the literature for the following odd-index companion to the Shapiro's Catalan convolution. Namely, let $C_\mathrm{odd}(z^2)=\dfrac{C(z)-C(-z)}{2z}$. Then $$ (zC(z))\circ(zC(4z))=zC_\mathrm{odd}(z), $$ where $\circ$ denotes composition of functions. Comparing the coefficients of both sides and cancelling a few factors yields $$ \sum_{k=0}^{n}{\binom{2n-2k}{n-k}\binom{n+k}{k}4^k}=\binom{4n+1}{2n}, $$ or, equivalently, $$ \sum_{k=0}^{n}{\binom{2k}{k}\binom{2n-k}{n-k}4^{n-k}}=\binom{4n+1}{2n}. $$