show this sum $\sum_{i=0}^{n}(-1)^{i-j}\binom{n+i}{i}\binom{n+k-i}{k-i}\binom{2n}{n+j-i}=\binom{2n}{n}$

Question

Let $n,k$ be positive integers. Show that $$\sum_{i=0}^{n}(-1)^{i-j}\binom{n+i}{i}\binom{n+k-i}{k-i}\binom{2n}{n+j-i}=\binom{2n}{n}$$ for all $j=0,1,2,\cdots,k$.

I don't know if this is an existing conclusion. After thinking for a long time, I found it difficult to deal with it.

---

Batominovski's edit:

However, when $k=0$ and $j=0$, the required sum is $$S=\sum_{i=0}^n(-1)^i\binom{n+i}{i}\binom{n-i}{-i}\binom{2n}{n-i}=\binom{n}{0}\binom{n}{0}\binom{2n}{n}=\binom{2n}{n}.$$ When $k=1$ and $j=0$, the required sum is $$S=\binom{n}{0}\binom{n+1}{1}\binom{2n}{n}-\binom{n+1}{1}\binom{n}{0}\binom{2n}{n-1}=(n+1)\binom{2n}{n}-(n+1)\binom{2n}{n-1}.$$ Because $\binom{2n}{n-1}=\binom{2n}{n+1}$, we have $$(n+1)\binom{2n}{n-1}=\binom{n+1}{1}\binom{2n}{n+1}=\binom{n}{1}\binom{2n}{n}=n\binom{2n}{n}.$$ Hence, $S=(n+1)\binom{2n}{n}-n\binom{2n}{n}=\binom{2n}{n}$. When $k=1$ and $j=1$, the required sum is $$S=-\binom{n}{0}\binom{n+1}{1}\binom{2n}{n+1}+\binom{n+1}{1}\binom{n}{0}\binom{2n}{n}=-(n+1)\binom{2n}{n+1}+(n+1)\binom{2n}{n}.$$ So, similar to the previous case, $S=\binom{2n}{n}$. How to prove this for generalized pairs $(k,j)$? Is there a combinatorial proof?

Answer 1

Numerical evidence indicates that the upper limit should be $k$ and not $n$ for this to hold including when $n\lt k.$ So we seek to show that

$$\sum_{q=0}^k (-1)^{q-j} {n+q\choose q} {n+k-q\choose k-q} {2n\choose n+j-q} = {2n\choose n}$$

where $0\le j\le k.$ The LHS is

$$(-1)^j [w^{n+j}] (1+w)^{2n} \sum_{q=0}^k (-1)^{q} {n+q\choose q} w^q {n+k-q\choose k-q} \\ = (-1)^j [w^{n+j}] (1+w)^{2n} [z^k] \frac{1}{(1+wz)^{n+1}} \frac{1}{(1-z)^{n+1}}.$$

The inner term is

$$\mathrm{Res}_{z=0} \frac{1}{z^{k+1}} \frac{1}{(1+wz)^{n+1}} \frac{1}{(1-z)^{n+1}}.$$

Residues sum to zero and the residue at infinity is zero by inspection. We get for the residue at $z=1$

$$(-1)^{n+1} \mathrm{Res}_{z=1} \frac{1}{z^{k+1}} \frac{1}{(1+wz)^{n+1}} \frac{1}{(z-1)^{n+1}} \\ = (-1)^{n+1} \mathrm{Res}_{z=1} \frac{1}{(1+(z-1))^{k+1}} \frac{1}{(1+w+w(z-1))^{n+1}} \frac{1}{(z-1)^{n+1}} \\ = \frac{(-1)^{n+1}}{(1+w)^{n+1}} \mathrm{Res}_{z=1} \frac{1}{(1+(z-1))^{k+1}} \frac{1}{(1+w(z-1)/(1+w))^{n+1}} \frac{1}{(z-1)^{n+1}} \\ = \frac{(-1)^{n+1}}{(1+w)^{n+1}} \sum_{q=0}^n {n+q\choose q} (-1)^q \frac{w^q}{(1+w)^q} (-1)^{n-q} {k+n-q\choose k} \\ = - \sum_{q=0}^n {n+q\choose q} \frac{w^q}{(1+w)^{n+1+q}} {k+n-q\choose k}.$$

Substitute into the coefficient extractor in $w$ to get

$$- (-1)^j \sum_{q=0}^n {n+q\choose q} {k+n-q\choose k} [w^{n+j-q}] (1+w)^{n-1-q}.$$

Now with $0\le q\le n-1$ and $j\ge 0$ we have $[w^{n+j-q}] (1+w)^{n-1-q} = 0.$ This leaves $q=n$ which yields

$$-(-1)^j {2n\choose n} {k\choose k} [w^j] \frac{1}{1+w} = - {2n\choose n}.$$

This is the claim. We have the result if we can show that the residue at $z=-1/w$ makes for a zero contribution. We get

$$\frac{1}{w^{n+1}} \mathrm{Res}_{z=-1/w} \frac{1}{z^{k+1}} \frac{1}{(z+1/w)^{n+1}} \frac{1}{(1-z)^{n+1}}.$$

This requires

$$\frac{1}{n!} \left(\frac{1}{z^{k+1}} \frac{1}{(1-z)^{n+1}}\right)^{(n)} = \frac{1}{n!} \sum_{q=0}^n {n\choose q} \frac{(-1)^q (k+q)!}{z^{k+1+q} \times k!} \frac{(n+n-q)!}{(1-z)^{n+1+n-q} \times n!} \\ = \sum_{q=0}^n {k+q\choose k} (-1)^q \frac{1}{z^{k+1+q}} {2n-q\choose n} \frac{1}{(1-z)^{2n+1-q}}.$$

Evaluate at $z=-1/w$ and restore the factor in front:

$$\frac{1}{w^{n+1}} \sum_{q=0}^n {k+q\choose k} (-1)^{k+1} w^{k+1+q} {2n-q\choose n} \frac{1}{(1+1/w)^{2n+1-q}}.$$

Applying the coefficient extractor in $w$ we get

$$(-1)^j [w^{n+j}] (1+w)^{2n} \frac{1}{w^{n+1}} w^{k+1+q} \frac{w^{2n+1-q}}{(1+w)^{2n+1-q}} \\ = (-1)^j [w^{n+j}] (1+w)^{q-1} w^{n+k+1} = (-1)^j [w^j] (1+w)^{q-1} w^{k+1} = 0$$

because $j\le k.$ This concludes the argument.

Answer 2

Rewrite the binomial coefficients in terms of factorials \begin{eqnarray*} \sum_{i=0}^{n} (-1)^{i-j} \frac{(n+i)!}{\color{red}{n!}i!} \frac{(n+k-i)!}{\color{red}{n!}(k-i)!} \frac{\color{red}{(2n)!}}{(n+j-i)!(n+i-j)!} =\color{red}{\frac{ (2n)!}{(n!)^2}}. \end{eqnarray*} $\color{red}{\text{Cancel}}$ and $\color{blue}{\text{create}}$ \begin{eqnarray*} \sum_{i=0}^{n} (-1)^{i-j} \frac{(n+i)!}{(n+i-j)!\color{blue}{j!}} \frac{(n+k-i)!}{(n+j-i)!\color{blue}{(k-j)!}} \frac{\color{blue}{k!}}{i!(k-i)!} = \color{blue}{\frac{k!}{j!(k-j)!}}. \end{eqnarray*} Thus, it suffices to show \begin{eqnarray*} \sum_{i=0}^{n} (-1)^{i-j} \binom{k}{i} \binom{n+i}{j} \binom{n+k-i}{k-j} =\binom{k}{j}. \end{eqnarray*} We shall use $2$ coefficient extractors \begin{eqnarray*} \binom{n+i}{j} &=& [x^j]: (1+x)^{n+i} \\ \binom{n+k-i}{k-j} &=& [y^{k-j}]:(1+y)^{n+k-i}. \end{eqnarray*} So \begin{eqnarray*} \sum_{i=0}^{n} (-1)^{i-j} \binom{k}{i} \binom{n+i}{j} \binom{n+k-i}{k-j} &=& \sum_{i=0}^{n} (-1)^{i-j} \binom{k}{i} [x^j]: (1+x)^{n+i} [y^{k-j}]:(1+y)^{n+k-i}\\ &=&[x^j][y^{k-j}]: \sum_{i=0}^{n} (-1)^{i-j} \binom{k}{i} (1+x)^{n+i} (1+y)^{n+k-i}\\ &=&[x^j][y^{k-j}]: (-1)^j \left( 1-\frac{1+x}{1+y} \right)^k (1+x)^{n} (1+y)^{n+k}\\ &=&[x^j][y^{k-j}]:(-1)^j \left( y-x \right)^k (1+x)^{n} (1+y)^{n}\\ &=& \binom{k}{j}. \\ \end{eqnarray*}