Consider lattice paths consisting of $2n$ steps, each of which is either $(1,1)$ or $(1,-1)$. The number of such lattice paths that return to the horizontal axis only at times that are a multiple of $4$ is given by $2^n \binom{n}{n/2}$. Can someone provide a combinatorial proof of this fact?
Background: A few months ago on math.SE I asked for a combinatorial proof of the identity $$\sum_{k=0}^n \binom{2k}{k} \binom{2n-2k}{n-k} (-1)^k = 2^n \binom{n}{n/2},$$ when $n$ is even.
The non-alternating version is $$\sum_{k=0}^n \binom{2k}{k} \binom{2n-2k}{n-k} = 4^n.$$ There are several combinatorial proofs of the non-alternating version, and I hoped to adapt one of them. One such proof is that $\binom{2k}{k} \binom{2n-2k}{n-k}$ counts the number of paths of length $2n$ with $2k$ steps above the horizontal axis and $2n-2k$ steps below it. Summing up over all values of $k$ gives the total number of paths of length $2n$, which is $2^{2n} = 4^n$. (I believe I saw this argument in Feller's An Introduction to Probability Theory and Its Applications. It's also in this note by David Callan.)
If we take the alternating version, the paths with positive parity are those with $2k$ steps above the axis for $k$ even, and the paths with negative parity are those with $2k$ steps above the axis for $k$ odd. For each path, break it every time it returns to the horizontal axis. This partitions each path into a number of segments equal to the number of times it returns to the axis. For every path that has a last segment consisting of $2j$ steps for $j$ odd, flip this segment over the horizontal axis. This mapping is an involution and changes the path's parity. Since every odd-parity path must have at least one such odd segment, $$\sum_{k=0}^n \binom{2k}{k} \binom{2n-2k}{n-k} (-1)^k$$ must count the number of paths that have no odd segment; i.e., the number of paths whose returns to the horizontal axis occur only at multiples of $4$. If $n$ is odd, there are no such paths without an odd segment, but if $n$ is even, there are apparently $2^n \binom{n}{n/2}$ of them.
However, I was unable to find an independent combinatorial proof that $2^n \binom{n}{n/2}$ counts the number of lattice paths of length $2n$ with no odd segments. (Again, an "odd" segment here is one of length $2j$, where $j$ is odd.) The math.SE question remained unanswered for over two months until I found a different way to prove the identity I was after combinatorially, but this other way doesn't involve lattice paths. After all the time I spent trying the lattice path approach I would like to see an independent combinatorial proof that $2^n \binom{n}{n/2}$ counts the number of lattice paths whose return times to the axis are multiples of $4$.
Best Answer
For the record, this question is answered in a pair of papers:
Gábor V. Nagy, A combinatorial proof of Shapiroʼs Catalan convolution, In Advances in Applied Mathematics, Volume 49, Issues 3–5, 2012, Pages 391-396
Péter Hajnal and Gábor V. Nagy. A Bijective Proof of Shapiro’s Catalan Convolution. Electronic Journal of Combinatorics, 21(2), 2014
In particular Lemma 7 of the first paper is, I think, a satisfactory answer to this question. The second paper gives a fully bijective proof.
Thanks to Richard Stanley.
These paths also have an interesting interpretation as NSEW lattice paths (where the set of steps is the four cardinal directions N, S, E, W). They correspond, under the usual bijection between one-dimensional paths of length $2k$ and two-dimensional paths of length $k$, to NSEW lattice paths from $(0,0)$ of length $n$ that intersect the $x$-axis only at positions with an even $x$-coordinate. In other words, to paths on the perforated plane obtained by removing (punching out) all the odd-numbered lattice points on the $x$-axis.