<s>[INST] Is this combinatorial identity a special case of Saalschutz's theroem? When I solved a question, the following combinatorial identity was used
$$
\sum_{k=0}^{n}(-1)^k{n\choose k}{n+k\choose k}{k\choose j}=(-1)^n{n\choose j}{n+j\choose j}.
$$
But to prove this identity is difficulty for me. I think it may be a special case of the Saalschutz's theroem, wchich is stated as follows
$$
\sum_{k=0}^{n}\frac{(-n)_k(a)_k(b)_k}{(1)_k(c)_k(1+a+b-c-n)_k}=\frac{(c-a)_n(c-b)_n}{(c)_n(c-a-b)_n},
$$
where $(a)_k=a\cdot (a+1)\cdots (a+k-1)$. If it isn't the special case of Saalschutz's theroem, can you present a proof of this identity? All hints, proofs and references are welcome.
 [/INST] Remark. Incorporates a correction by Markus Scheuer.
Suppose we seek to evaluate
$$S_j(n) = \sum_{k=0}^n (-1)^k {n\choose k}
{n+k\choose k} {k\choose j}$$
which is claimed to be
$$(-1)^n {n\choose j}{n+j\choose j}.$$
Introduce
$${n+k\choose k}
= \frac{1}{2\pi i}
\int_{|z|=\epsilon} \frac{(1+z)^{n+k}}{z^{k+1}} \; dz$$
and
$${k\choose j}
= \frac{1}{2\pi i}
\int_{|w|=\epsilon} \frac{(1+w)^{k}}{w^{j+1}} \; dw.$$
This yields for the sum
$$\frac{1}{2\pi i}
\int_{|z|=\epsilon} \frac{(1+z)^{n}}{z}
\frac{1}{2\pi i}
\int_{|w|=\epsilon} \frac{1}{w^{j+1}}
\sum_{k=0}^n (-1)^k {n\choose k} \frac{(1+z)^k (1+w)^k}{z^k} 
\; dw \; dz
\\ = \frac{1}{2\pi i}
\int_{|z|=\epsilon} \frac{(1+z)^{n}}{z}
\frac{1}{2\pi i}
\int_{|w|=\epsilon} \frac{1}{w^{j+1}}
\left(1-\frac{(1+w)(1+z)}{z}\right)^n
\; dw \; dz
\\ = \frac{1}{2\pi i}
\int_{|z|=\epsilon} \frac{(1+z)^{n}}{z^{n+1}}
\frac{1}{2\pi i}
\int_{|w|=\epsilon} \frac{1}{w^{j+1}}
\left(-1-w-wz\right)^n
\; dw \; dz
\\ = \frac{(-1)^n}{2\pi i}
\int_{|z|=\epsilon} \frac{(1+z)^{n}}{z^{n+1}}
\frac{1}{2\pi i}
\int_{|w|=\epsilon} \frac{1}{w^{j+1}}
\left(1+w+wz\right)^n
\; dw \; dz
.$$
This is
$$\frac{(-1)^n}{2\pi i}
\int_{|z|=\epsilon} \frac{(1+z)^{n}}{z^{n+1}}
\frac{1}{2\pi i}
\int_{|w|=\epsilon} \frac{1}{w^{j+1}}
\sum_{q=0}^n {n\choose q} w^q (1+z)^q
\; dw \; dz.$$
Extracting the residue at $w=0$ we get
$$\frac{(-1)^n}{2\pi i}
\int_{|z|=\epsilon} \frac{(1+z)^{n}}{z^{n+1}}
{n\choose j} (1+z)^j \; dz
\\ = {n\choose j}  \frac{(-1)^n}{2\pi i}
\int_{|z|=\epsilon} \frac{(1+z)^{n+j}}{z^{n+1}}\; dz
\\ = (-1)^n {n\choose j} {n+j\choose n}.$$
thus proving the claim.
</s>