# 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. – Somos 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}$. – MTyson 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'. – Peter Heinig Oct 16 '17 at 7:18
• Crossposted at artofproblemsolving.com/community/… – darij grinberg 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? – Sergey Dovgal 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! – Shahrooz Janbaz 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? – Vincent 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. – Fedor Petrov 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})$. – Max Alekseyev 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. – Alexander Burstein 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. – Robin Houston 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$? – Fedor Petrov 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$. – Max Alekseyev Oct 16 '17 at 19:24
• Ok, but this could be mentioned in the answer, I think. – Fedor Petrov Oct 16 '17 at 20:04
• I assume it's a common knowledge. – Max Alekseyev Oct 16 '17 at 20:06