# 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}$

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

• The numbers you have come from the OEIS sequence A091044 but I don't see anything there now that would lead to a proof. Oct 15 '17 at 14:44
• Note that without the squares, the LHS counts the number of paths down Pascal's triangle from $(n,k)=(0,0)$ to $(a+b,a)$ passing through a marked point $(i+j,i)$. Since each path contains $a+b+1$ points, that sum equals $(a+b+1){a+b\choose a}$. Oct 16 '17 at 0:25
• It would be very interesting if someone knowing much about the Wilf-Zeilberger method would write a relevant comment on whether this identity nowadays is regarded as 'automatically provable'. Oct 16 '17 at 7:18
• Crossposted at artofproblemsolving.com/community/… Oct 16 '17 at 8:50
• As I know from some talks, WZ can be sometimes inefficient, but recently guys invented a new more efficient algorithm to do the job. arxiv.org/abs/1510.07487 arxiv.org/abs/1404.5069 Offtopic: Is there a simple explanation why such kinds of questions "combinatorial identity of type sum of product of binomials having linear combinations as arguments" are so popular on MO? Oct 17 '17 at 14:51

Denote $h(x,y)=\sum_{i,j\geqslant 0} \binom{i+j}i x^iy^j=\frac1{1-(x+y)}$, $f(x,y)=\sum_{i,j\geqslant 0} \binom{i+j}i^2 x^iy^j$. We want to prove that $2xyf^2(x^2,y^2)$ is an odd (both in $x$ and in $y$) part of the function $h(x,y)$. In other words, we want to prove that $$2xyf^2(x^2,y^2)=\frac14\left(h(x,y)+h(-x,-y)-h(x,-y)-h(-x,y)\right)=\frac{2xy}{1-2(x^2+y^2)+(x^2-y^2)^2}.$$ So, our identity rewrites as $$f(x,y)=(1-2(x+y)+(x-y)^2)^{-1/2}=:f_0(x,y)$$ This is true for $x=0$, both parts become equal to $1/(1-y)$. Next, we find a differential equation in $x$ satisfied by the function $f_0$. It is not a big deal: $$\left(f_0(1-2(x+y)+(x-y)^2)\right)'_x=(x-y-1)f_0.$$ Since the initial value $f_0(0,y)$ and this relation uniquely determine the function $f_0$, it remains to check that this holds for $f(x,y)$, which is a straightforward identity with several binomials. Namely, comparing the coefficients of $x^{i-1}y^j$ we get $$i\left(\binom{i+j}j^2-2\binom{i+j-1}j^2-2\binom{i+j-1}i^2+\binom{i+j-2}i^2+\binom{i+j-2}j^2-2\binom{i+j-2}{i-1}^2\right)$$ for $(f(1-2(x+y)+(x-y)^2))'_x$ and $$\binom{i+j-2}j^2-\binom{i+j-1}j^2-\binom{i+j-2}{j-1}^2$$ for $(x-y-1)f$. Both guys are equal to $$-2\frac{j}{i+j-1}\binom{i+j-1}{j}^2.$$

• Nice one dear Petrov! Oct 16 '17 at 11:02
• Can you please explain how $xyf^2(x^2, y^2)$ being an odd part of $h(x, y)$ relates to the question being asked? Oct 16 '17 at 15:08
• @Vincent look at a coefficient of $x^{2a+1}y^{2b+1}$ in $xyf(x^2,y^2)f(x^2,y^2)$. It is nothing but the left hand side of the desired identity. Oct 16 '17 at 15:33
• The identity $f(x,y)=f_0(x,y)$ can be also obtained by Lagrange Inversion. Or, derived from the g.f. $F(x,y)$ given in my answer as $f(x,y)=F(x,\frac{y}{x})$. Oct 16 '17 at 19:10
• Is it true that $f(0)＝f_0(0),(f(1-2(x+y)+(x-y)^2))_x'＝(x-y-1)f,(f_0(1-2(x+y)+(x-y)^2))'＝(x-y-1)f_0⇒f＝f_0？$
– ken
Oct 17 '17 at 5:38

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:

1. 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;
2. 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.

• This is really nice. Can this argument be modified somehow to show that, for any permutation $\pi$ of $\{0,1,\dots,n\}$, we have $\sum_{i,j=0}^{n}\binom{i+j}{i}\binom{2n-i-j}{n-i}\binom{\pi(i)+\pi(j)}{\pi(i)}\binom{2n-\pi(i)-\pi(j)}{n-\pi(i)}>\binom{2n+1}{n+1}^2$? I had to prove this once a while ago, but could not find any argument using a natural lattice path interpretation, like yours above. Nov 17 '17 at 1:44
• @AlexanderBurstein If it can, I don’t yet see how. I’ll let you know if I think of anything. Nov 23 '17 at 15:38

Let us denote $$S=\sum_{i,j \ge 0} \binom{i+j}{i}^2 \binom{(a-i)+(b-j)}{a-i}^2.$$

First, let $s=i+j$ so that $$S = \sum_{s\geq 0}\sum_{i=0}^s \binom{s}{i}^2 \binom{a+b-s}{a-i}^2.$$ Consider the generating function $$F(x,y) = \sum_{s,i} \binom{s}{i}^2 x^i y^s = (1-2y+y^2-2xy-2xy^2+x^2y^2)^{-1/2}.$$ Then $S$ is nothing else but the coefficient of $x^a y^{a+b}$ in $$F(x,y)^2 = (1-2y+y^2-2xy-2xy^2+x^2y^2)^{-1}$$ $$= \frac{1}{4y\sqrt{x}}\left(\frac{1}{1-y(1+x+2\sqrt{x})} - \frac{1}{1-y(1+x-2\sqrt{x})}\right)$$ $$= \frac{1}{4y\sqrt{x}}\left(\frac{1}{1-y(1+\sqrt{x})^2} - \frac{1}{1-y(1-\sqrt{x})^2}\right).$$ (derivation simplified)

The coefficient of $y^{a+b}$ equals $$[y^{a+b}]\ F(x,y)^2 =\frac{1}{4} \frac{(1+\sqrt{x})^{2(a+b+1)} - (1-\sqrt{x})^{2(a+b+1)}}{\sqrt{x}}.$$ Now we trivially conclude that $$S = [x^ay^{a+b}]\ F(x,y)^2 = \frac{1}{2}\binom{2(a+b+1)}{2a+1}.$$

UPDATE. Alternatively to computing the coefficient of $x^ay^{a+b}$, one can follow the venue of Fedor Petrov's proof. This way one needs to consider the generating function $$G(x,y) = \sum_{m,n}\binom{m}{n} x^ny^m = \frac{1}{1-y-xy}$$ and verify that $$8xy^2F(x^2,y^2)^2 = G(x,y) + G(x,-y) - G(-x,y) - G(-x,-y).$$

• How do you get the formula for $F$? Oct 16 '17 at 19:21
• @FedorPetrov: Notice that $\binom{s}{i}^2 = [x^iz^s]\ ((1+xz)(1+z))^s$ and use Lagrange inversion w.r.t. variable $z$. Oct 16 '17 at 19:24
• Ok, but this could be mentioned in the answer, I think. Oct 16 '17 at 20:04
• I assume it's a common knowledge. Oct 16 '17 at 20:06