TITLE: Combinatorial identity: $\sum_{i,j \ge 0} \binom{i+j}{i}^2 \binom{(a-i)+(b-j)}{a-i}^2=\frac{1}{2} \binom{(2a+1)+(2b+1)}{2a+1}$
QUESTION [30 upvotes]: In my research, I found this identity and as I experienced, it's surely right. But I can't give a proof for it.
Could someone help me?
This is the identity:
let $a$ and $b$ be two positive integers; then:
$\sum_{i,j \ge 0} \binom{i+j}{i}^2 \binom{(a-i)+(b-j)}{a-i}^2=\frac{1}{2} \binom{(2a+1)+(2b+1)}{2a+1}$.

REPLY [17 votes]: 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.
{"set_name": "stack_exchange", "score": 30, "question_id": 283540}