Return to Question

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 if 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}. $$

Update: Since $C_{2n}$ is the number of grand Dyck paths from $(0,0)$ to $(4n,0)$ avoiding points $(4k+2,0)$ for integer $k$, we can partition these grand Dyck paths into raised Dyck paths, or their reflections across the $x$-axis, between successive returns to the $x$-axis), so that that $$ C_\mathrm{even}(z)=\frac{1}{1-2zC_\mathrm{odd}(z)}, $$ and thus $$ C_\mathrm{even}(z)=\frac{1}{1-2zC(z)}\circ (zC(4z))=B(z)\circ (zC(4z)), $$ where $B(z)=\frac{1}{\sqrt{1-4z}}$ is the generating function for the central binomial coefficients. This, in turn, lets us recover Shapiro's Catalan convolution, as $$ (C_\mathrm{even}(z))^2=B^2(z)\circ (zC(4z))=\frac{1}{1-4z}\circ (zC(4z))=\frac{1}{1-4zC(4z)}=C(4z). $$

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 if 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}. $$

Update: Since $C_{2n}$ is the number of grand Dyck paths from $(0,0)$ to $(4n,0)$ avoiding points $(4k+2,0)$ for integer $k$, we can partition these grand Dyck paths into raised Dyck paths, or their reflections across the $x$-axis, between successive returns to the $x$-axis), so that $$ C_\mathrm{even}(z)=\frac{1}{1-2zC_\mathrm{odd}(z)}, $$ and thus $$ C_\mathrm{even}(z)=\frac{1}{1-2zC(z)}\circ (zC(4z))=B(z)\circ (zC(4z)), $$ where $B(z)=\frac{1}{\sqrt{1-4z}}$ is the generating function for the central binomial coefficients. This, in turn, lets us recover Shapiro's Catalan convolution, as $$ (C_\mathrm{even}(z))^2=B^2(z)\circ (zC(4z))=\frac{1}{1-4z}\circ (zC(4z))=\frac{1}{1-4zC(4z)}=C(4z). $$

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 if 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}. $$

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 if 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}. $$

Update: Since $C_{2n}$ is the number of grand Dyck paths from $(0,0)$ to $(4n,0)$ avoiding points $(4k+2,0)$ for integer $k$, we can partition these grand Dyck paths into raised Dyck paths, or their reflections across the $x$-axis, between successive returns to the $x$-axis), so that that $$ C_\mathrm{even}(z)=\frac{1}{1-2zC_\mathrm{odd}(z)}, $$ and thus $$ C_\mathrm{even}(z)=\frac{1}{1-2zC(z)}\circ (zC(4z))=B(z)\circ (zC(4z)), $$ where $B(z)=\frac{1}{\sqrt{1-4z}}$ is the generating function for the central binomial coefficients. This, in turn, lets us recover Shapiro's Catalan convolution, as $$ (C_\mathrm{even}(z))^2=B^2(z)\circ (zC(4z))=\frac{1}{1-4z}\circ (zC(4z))=\frac{1}{1-4zC(4z)}=C(4z). $$

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}. $$

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 if 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}. $$