MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
Could you be more precise about the argument for the non-alternating version? Sorry, I just am very surprised to see anything combinatorial on less than 3 pages for that thing – darij grinberg Jan 29 '12 at 0:52
@darij: I've added a reference to a note by Callan that gives the argument for the non-alternating version. It's more than three pages. :) – Mike Spivey Jan 29 '12 at 5:10
@darji grinberg: Let me see if the size of this margin, um comment, suffices. First, $2^{2n}$ counts paths of length $2n+1$ ending above the axis. Cut at the last visit to the axis into a balanced path of length $2k$ (obviously $\tbinom{2k}k$ possibilities), then an upstep, then a path of length $2(n-k)$ never descending below its starting point. To see that $\tbinom{2(n-k)}{n-k}$ counts the latter, map it bijectively to a balanced path by reversing every step that is last to attain a level $\leq$ half the ending level. The inverse mapping reverses every step first attaining a level below $0$. – Marc van Leeuwen Jan 29 '12 at 14:31

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.