A combinatorial proof of the identity $\sum\limits_{k=0}^n\binom{2k}{k}\binom{2(n-k)}{n-k}=4^n$

You can prove this identity using paths with steps of size $\pm1$. There are a total of $4^n$ such paths of length $2n$ starting at $(0,0)$. Partition this set of paths according to the final visit to the $x$-axis, call that position $(2k,0).$

It is pretty clear that the number of paths from $(0,0)$ to $(2k,0)$ is $2k\choose k$; this is the red part of the diagram. It is not so clear, but is true, that the number of paths of length $2n-2k$ that start at $(2k,0)$ and do not touch the $x$-axis is ${2(n-k)\choose n-k}$. This is the black part of the diagram.

enter image description here


To find a combinatorial argument for this identity has a long history. See the references below and also Phira's answer here. The following diagram fills a gap in my argument above by showing a bijection between balanced paths that start with an upstep and strictly positive paths.

enter image description here

Starting with a balanced path, keep the initial upstep, then color red until you reach the minimum value for the first time. Reverse the red section and swap the red and black sections, and connect them to create a strictly positive path.

Starting with a strictly positive path, keep the initial upstep. Now the path ends at $(2n,2a)$ for some $a>0$. Begin at the right and color red until you reach level $a$ for the first time. Reverse the red section and swap the red and black sections, and connect them to create a balanced path.

Similarly, balanced paths with an initial downstep are in one-to-one correspondence with strictly negative paths. Therefore the set of all balanced paths is in one-to-one correspondence with paths that don't touch the $x$-axis except at $(0,0)$.

  1. Counting and Recounting: The Aftermath by Marta Sved, Math. Intelligencer 6 (1984), no. 4, 44–45.

  2. Bijections for the identity $4^n=\sum_{k=0}^n {2k\choose k}{2(n-k)\choose n-k}$ by David Callan

  3. Two New Bijections on Lattice Paths by Glenn Hurlbert and Vikram Kamat, arXiv:math/0609222 [math.CO]