# Proofs of some combinatorial identities

Just wondering if anyone knows any references in the literature to bijections corresponding to the following simple generating function identities. Let $B(z)=\dfrac{1}{\sqrt{1-4z}}$ and $C(z)=\dfrac{1-\sqrt{1-4z}}{2z}$, the generating functions of the central binomial coefficients and Catalan numbers, respectively. I'm looking for bijections corresponding to the following identities: $$B(z)B(-z)=B(4z^2),$$ $$\frac{C(z)+C(-z)}{2}=B(z)(1-2zC(4z^2))=B(-z)(1+2zC(4z^2))$$ and, taking the product of the last two expressions in the second identity and using the first identity and the fact that $1-zC^2=C/B$, $$\left(\frac{C(z)+C(-z)}{2}\right)^2=C(4z^2).$$ Thanks.

Update: In a similar vein, one can try to prove other such identities. For example, let $E(z)=\dfrac{1}{\sqrt{1-2z-3z^2}}$ be the generating function of the central trinomial coefficients, then $$E(4z)=B(-z)B(3z) \quad \text{and} \quad E(2z)E(-2z)=B(z^2)B(9z^2).$$

• Care to state the exact identities on the level of binomial coefficients? I'm asking because sometimes the same generating-function identity can become two different binomial-coefficient identities just by differently canceling its denominators; a bijective proof for one doesn't translate into a bijective proof for the other. (Also, I'm asking because I'm lazy.) – darij grinberg Oct 1 '17 at 6:55
• (Feeling a bit lazy myself here.) The first one is a convolution of signed and unsigned central binomial coefficients. The second one is even-indexed Catalan numbers as two different convolutions. Perhaps, it might make sense there to divide both sides by $1-2zC(4z^2)$, so we have $B(z)$ on the one side and both series with positive coefficients on the other side. The last one is a convolution of even-indexed Catalan numbers with themselves. – Alexander Burstein Oct 1 '17 at 7:18
• "A combinatorial proof of Shapiroʼs Catalan convolution" by Gábor V.Nagy (Advances in Applied Mathematics 49 (2012), 391-396) seems to be very closely related. Except maybe actually your question was inspired by that paper? – მამუკა ჯიბლაძე Oct 1 '17 at 8:57
• @მამუკაჯიბლაძე Thanks! No, I haven't seen this paper before. – Alexander Burstein Oct 1 '17 at 14:22
• Okay, so your first equality is $\sum\limits_{k=0}^n \left(-1\right)^k \dbinom{2k}{k} \dbinom{2\left(n-k\right)}{n-k} = \left[n \text{ is even}\right] 2^n \dbinom{n}{n/2}$. This looks like something I've seen before, but not sure if I've ever seen a combinatorial proof. Obviously it would be involutive rather than bijective, due to the alternating signs. – darij grinberg Oct 1 '17 at 23:48

Partial answer: Your first identity is $$\sum\limits_{k=0}^n \left(-1\right)^k \dbinom{2k}{k} \dbinom{2\left(n-k\right)}{n-k} = \left[n \text{ is even}\right] 2^n \dbinom{n}{n/2} ,$$ where I am using the Iverson bracket notation. (That is, $[\mathcal{A}]$ denotes the truth value of a statement $\mathcal{A}$.)

This identity is proven in: Michael Z. Spivey, A Combinatorial Proof for the Alternating Convolution of the Central Binomial Coefficients. This paper actually arose from an m.se question.

Disclaimer: I have not read the proof.

It's not the formally published literature, but unless I'm mistaken, the last of your three identities appears in Stanley's list of bijective proof problems (dated 2009) as number 194. He says there that finding a combinatorial bijection for the identity is an open problem. (He suggests some of the open problems in the list as being of particular interest, however, and 194 is not one of those.)

This suggests rather strongly that a bijective proof for the third identity isn't known, or at least wasn't known as of 2009.

I always found it a little surprising that this one was open. Both sides of the identity count natural things: The LHS counts the number of lattice paths from $(0,0)$ to $(2n,2n)$ that do not go above the diagonal, and that return to the diagonal at a distinguished point $(2k,2k)$. The RHS the number of lattice paths from $(0,0)$ to $(n,n)$ that do not go above the diagonal, and whose edges/steps are 2-colored.

• It is known now. See the 2012 paper by Nagy listed in the comments to the question. – Alexander Burstein Oct 11 '17 at 6:17
• Doh! I hadn't known about that paper either. I could've saved myself some time thinking about the problem at some point. @მამუკა ჯიბლაძე should post as an answer. – Russ Woodroofe Oct 11 '17 at 6:22
• I am very sorry about that -- I wanted very much to do it but to my shame just could not find enough time even to read the paper in full to understand well enough what is happening there in detail. If you or somebody else can make an answer out of it I would be very glad - even relieved, in fact. – მამუკა ჯიბლაძე Dec 10 '17 at 7:31