When this identity was posted, it struck me as something that ought to have a combinatorial explanation. I have now found one, using a decomposition of NSEW lattice paths: paths in $\mathbb{Z}^2$ consisting of unit steps in the direction N, S, E or W. Many of the ideas here may be found in [GKS], though not the decomposition itself.

### The expression $\frac12{2a+1\ +\ 2b+1\choose2a+1}$ counts paths of $(a+b+1)$ steps that start at $(0,0)$ and end on the half-line $(a-b,\geq0)$.

To see this, decompose each path step as two half-steps $±\left[\begin{smallmatrix}½\\½\end{smallmatrix}\right]$ and $±\left[\begin{smallmatrix}½\\-½\end{smallmatrix}\right]$. If the $+$ option is chosen for $(2a+1)$ of the $2(a+b+1)$ half-steps, and the $-$ option for the other $(2b+1)$, then the $x$-coordinate of the endpoint is $\frac12((2a+1)-(2b+1))=a-b$. Thus there are ${2a+1\ +\ 2b+1\choose2a+1}$ paths of $(a+b+1)$ steps from $(0,0)$ to $x=a-b$. By parity, the end position must have an odd-numbered $y$-coordinate. Reflection in the $x$-axis is therefore a fixpoint-free involution, so half of these paths end on the half-line $(a-b,\geq0)$.

### Such a path may be split into a pair of paths with $(a+b)$ steps in total.

The endpoint of the path is $(a-b, 2k+1)$ for some $k\in\mathbb N$. At least one step of the path must therefore be an N step from $(c,2k)$ to $(c,2k+1)$ for some $c$. Remove the first such step, to give a pair of paths with $a+b$ steps altogether:

- A path of $n$ steps from $(0,0)$ to $(c,2k)$ that does not cross the line $y=2k$, which we can think of as a 180° rotation of a path from $(0,0)$ to $(c,2k)$ that does not cross the $x$-axis;
- A path of $a+b-n$ steps from $(c,2k+1)$ to $(a-b,2k+1)$, which we can think of as a translation of a path from $(0,0)$ to $(a-b-c,0)$.

This is clearly a bijection.

### There are ${i+j\choose i}^2$ paths of $(i+j)$ steps from $(0,0)$ to $(i-j,0)$.

The four directions N,S,E,W may be obtained by starting with $\left[\begin{smallmatrix}-1\\0\end{smallmatrix}\right]$ and adding neither, one, or both of $\left[\begin{smallmatrix}1\\1 \end{smallmatrix}\right]$ and $\left[\begin{smallmatrix}1\\-1\end{smallmatrix}\right]$. Build a path of $i+j$ steps, initially all $\left[\begin{smallmatrix}-1\\0\end{smallmatrix}\right]$. Add $\left[\begin{smallmatrix}1\\1\end{smallmatrix}\right]$ to $i$ of the steps and, independently, add $\left[\begin{smallmatrix}1\\-1\end{smallmatrix}\right]$ to $i$ of the steps.

### There are also ${i+j\choose i}^2$ paths of $(i+j)$ steps from $(0,0)$ to $(i-j,\geq0)$ that do not cross the $x$-axis.

There is a bijection between these paths and the paths of the previous section using a raising/lowering transformation [GKS]. Suppose we have a path from $(0,0)$ to $(i-j,0)$ that may cross the $x$-axis.

- While the path crosses the $x$-axis, do the following:
- Take the initial segment of the path up to the first time it touches the line $y=-1$, and reflect this initial segment about that line. Then translate the entire path up by two units, so it starts at $(0,0)$ again and ends two units higher than before on $x=i-j$.

I hope it is clear that this process is reversible. (In reverse: while the endpoint is above the $x$-axis, translate the path two units down, then take the initial segment from $(0,-2)$ to the first intersection with $y=-1$ and reflect this initial segment about that line.)

### Putting it together

Now we have all the ingredients we need. Let us count the pairs of paths as described above. Since $n$ and $c$ have the same parity, we may write $n=i+j$ and $c=i-j$ for $i\in[0,a]$, $j\in[0,b]$.

- There are ${i+j\choose i}^2$ paths of $(i+j)$ steps from $(0,0)$ to $(i-j,\geq 0)$ that do not cross the $x$-axis.
- There are ${a-i\ +\ b-j\choose a-i}^2$ paths of $(a+b)-(i+j)$ steps from $(0,0)$ to $(a-b-(i-j),0)$.

So in total there are

$$\sum_{i=0}^a\sum_{j=0}^b{i+j\choose i}^2{a-i\ +\ b-j\choose a-i}^2$$

such pairs, as required.

[GKS] Richard K. Guy, C. Krattenthaler and Bruce E. Sagan (1992). *Lattice paths, reflections, & dimension-changing bijections*, Ars Combinatoria, 34, 3–15.

Wilf-Zeilberger methodwould write a relevant comment on whether this identity nowadays is regarded as 'automatically provable'. $\endgroup$ – Peter Heinig Oct 16 '17 at 7:18