Combinatorial proof of a certain binomial identity

Question

Let $n$, $p$, $q$ be non-negative integers. Then $$ \sum_{k=0}^n{2k+2p\choose k+p,k,p}{2(n-k)+2q\choose n-k+q,n-k,q}=4^n{2p\choose p}{2q\choose q}{n+p+q\choose n}.\tag{$\heartsuit$}\label{heart} $$ In particular, for $p=q=0$ \eqref{heart} reads as $$ \sum_{k=0}^n{2k\choose k}{2(n-k)\choose n-k}=4^n.\tag{$\clubsuit$}\label{club} $$ There are known nice combinatorial (essentially bijective) proofs of \eqref{club}, I wonder whether there is anything equally nice working for \eqref{heart}.

For what it's worth, \eqref{heart} is just Chu–Vandermonde identity $\sum {x\choose k}{y\choose n-k}={x+y\choose n}$ for $x=-p-1/2$, $y=-q-1/2$.

Answer 1

$\newcommand{U}{\uparrow} \newcommand{D}{\downarrow} \newcommand{F}{\nearrow} \newcommand{G}{\searrow} \newcommand{O}{\otimes}$Fascinating question. Here goes an involved, but essentially bijective, argument.

We write "$S$-walk" for a lattice walk starting at the origin, with each step an element of the collection $S$. Steps in $S$ can be $\U = (0, 1)$, $\D = (0, -1)$, $\F = (1, 1)$, and $\O = (0, 0)$ (used as a marker). E.g. "$\U\D$-walk" is a regular 1D unit walk on the $x = 0$ axis. Length of a walk is the number of transitions (regardless of, say, Euclidean distance travelled).

For a non-negative $p$ we define $R_p$ and $L_p$ as sets of even-length $\U\D\F$-walks containing exactly $p$ $\F$'s, and additionally:

• $R_p$ finish at the point $(p, 0)$,
• $L_p$ visit $(p, 0)$ at least once, and never return to the origin after the start.

Sets $R_p$ and $L_p$ are in length-preserving bijection. When $p = 0$, define the bijection$f_0: R_0 \to L_0$ as follows:

• Suppose $r \in R_0$ starts with a $\U$ (the other case is symmetrical). Locate all $\U$ transitions that reach each positive $y$ for the first time in $r$, and change them into $\D$'s.
• Suppose $l \in L_0$ stays below $y = 0$ (the other case is symmetrical). Let $-2h$ be the final $y$-coodinate of $l$. Find $\D$'s that reach $y= -1, \ldots, -h$ for the last time in $l$, and change them into $\U$'s.

Otherwise, use $f_0$ to obtain $f_p: R_p \to L_p$:

• Any $r_p \in R_p$ splits uniquely as $r_p = r_0 w$, where $r_0 \in R_0$, $w \in R_p \cap L_p$. Put $f_p(r_p) = w f_0(r_0)$.
• Any $l_p \in L_p$ splits uniquely as $l_p = w l_0$, where $l_0 \in L_0$, $w \in R_p \cap L_p$. Recover $f_p(f^{-1}(l_0) w) = l_p$.

Let $W_{p, q}$ be the set of even-length $\U\D\F$-walks that contain exactly $(p + q)$ $\F$'s, and visit both points $(p, 0)$ and $(p + q, 0)$ at least once. Any walk $w \in W_{p, q}$ splits uniquely as $w = r_p l_q$, where $r_p \in R_p$, $l_q \in L_q$ (split at the last visit of $(p, 0)$). Observe that there are ${2(p + k) \choose p, k, p + k}$ walks of length $2(p + k)$ in $R_p$ (as well as $L_p$). This proves that LHS$(\heartsuit)$ is the number of walks in $W_{p, q}$ of length $2(n + p + q)$. Note that when $p = q = 0$, this number is trivially $4^n$, so we have recovered a bijective proof of $(\clubsuit)$.

In general, consider the following recursive algorithm $g$:

• Input: an $\U\D\F$-walk $w$.
• Output: an encoding $\U\D\O$-walk $x$, and a hint $\F\D$-walk $h$.

0. Initialize $x$ and $h$ to be empty.
1. If $w$ does not contain $\F$'s, append $w$ to $x$ and finish.
2. Split $w = uv$ at the first visit of a point $(x, 0)$ with $x > 0$. If such a split does not exist, fail.
3. Split $u = ab$, where $a \in R_0, b \in R_x \cap L_x$. If $b$ stays below $y = 0$, reverse the order of steps in $b$ (it now stays above $y = 0$).
4. Locate the $\F$ in $b$ that occurs at the lowest height $y$, choosing the rightmost $\F$ to break ties. Use it to split $b = b_1 \F b_2 \D$.
5. Put $w' = b_2 b_1$. Note that $w' \in R_{x - 1}$, and all $\F$'s in $w'$ happen above $y = 0$ (which means that no reverses on step 3 will happen down this recursion branch). Also, the split $w' = b_2 b_1$ occurs at the last visit of the lowest $y$ in $w'$.
6. Let $(x', h') = g(w')$. Append $f_0(a) \O$ to $x'$, and replace $h'$ with $\F h'\D$. Additionally, if a reverse happened on step 3, reverse the order of steps in $h'$.
7. Append $x'$ to $x$, $h'$ to $h$, and replace $w$ with $v$. Return to step 1.

The algorithm finishes succesfully on a walk with $p$ $\F$'s iff the walk visits $(p, 0)$. Crucially, the algorithm is reversible. Informally:

• The encoding $x$ looks like $w_0 \O w_1 \O \ldots \O w_p$, where all $w_i$ are $\U\D$-walks of even length. $w_p$ is simply the tail of $w$ after visiting $(p, 0)$. Every other $w_i$ is built as an $R_0$ tail of some $w'$, followed by some $f_0(a) \in L_0$, therefore the split is unique (recall bijective proof of $(\clubsuit)$).
• $h$, as a "signed" balanced bracket sequence, encodes the recursion tree of $g$, as well as which chunks of the input were flipped.

Further still, notice that the resulting $h$ visits the same set of points of $y = 0$ as initial $w$.

Consider running $g$ on elements of $W_{p, q}$ of length $2(n + p + q)$. We argue that there are RHS$(\heartsuit)$ possible outputs $(x, h)$:

• $x$ consists of $(p + q)$ $\O$'s, and $(2n)$ $\U\D$'s, grouped in even-length blocks. Thus there are $4^n {n + p + q \choose n}$ possible $x$'s (choose the sequence of $\U\D$'s, and interleave the $\O$'s with consecutive $\U\D$ pairs).
• $h$ is an $\F\D$-walk of length $2(p + q)$ visiting $(p, 0)$ and finishing at $(p + q, 0)$. There are ${2p \choose p}{2q \choose q}$ of them.

By bijective nature of $g$, reversing $g$ on any of those pairs $(x, h)$ gives an element of $W_{p, q}$ of length $2(n + p + q)$. This concludes the proof.

Note that $g$ allows to establish more product representations for sizes of similarly defined $W_{p_1, \ldots, p_k}$ visiting many prescribed points on $y = 0$, but matching LHS sums have to look differently.