<s>[INST] Identity involving binomial coefficients: $\sum_{j=0}^i (-1)^{i+j}\binom {n-j}{i-j}\binom mj=\sum_{j=0}^i (-1)^{i+j}\binom {n-j+k}{i-j}\binom {m+k}j$ Can you help me prove the following identity? I know it holds because I simulated it.
For positive integers $n,m,k$ and for $i=0,\ldots,n$ and for $n \leq m$ we have:
$$\sum_{j=0}^i (-1)^{i+j}\binom {n-j} {i-j} \binom {m}{j} = \sum_{j=0}^i (-1)^{i+j}\binom {n-j+k} {i-j} \binom {m+k}{j}$$
 [/INST] This can be done using a basic complex variables technique.
Suppose we seek to verify that
$$\sum_{j=0}^q {m\choose j} (-1)^j {n-j\choose q-j}
= \sum_{j=0}^q {m+k\choose j} (-1)^j {n-j+k\choose q-j} .$$
We will treat the case $q=m$ and $n\le m.$
Introduce the two integral representations
$${n-j\choose q-j}
= \frac{1}{2\pi i} 
\int_{|z|=\epsilon} \frac{1}{z^{q-j+1}} (1+z)^{n-j} \; dz$$
and 
$${n-j+k\choose q-j}
= \frac{1}{2\pi i} 
\int_{|z|=\epsilon} \frac{1}{z^{q-j+1}} (1+z)^{n-j+k} \; dz$$
This gives the following integral for the sum on the LHS 
$$\frac{1}{2\pi i} 
\int_{|z|=\epsilon} 
\sum_{j=0}^m {m\choose j} (-1)^j
\frac{1}{z^{q-j+1}} (1+z)^{n-j} \; dz
\\ = \frac{1}{2\pi i} 
\int_{|z|=\epsilon} 
\frac{(1+z)^n}{z^{q+1}}
\sum_{j=0}^m {m\choose j} (-1)^j
\frac{z^j}{(1+z)^j} \; dz
\\ = \frac{1}{2\pi i} 
\int_{|z|=\epsilon} 
\frac{(1+z)^n}{z^{q+1}}
\left(1-\frac{z}{1+z}\right)^m \; dz
\\ = \frac{1}{2\pi i} 
\int_{|z|=\epsilon} 
\frac{1}{z^{q+1}}
\frac{1}{(1+z)^{m-n}} \; dz.$$
We get the following integral for the sum on the RHS
$$\frac{1}{2\pi i} 
\int_{|z|=\epsilon} 
\sum_{j=0}^m {m+k\choose j} (-1)^j
\frac{1}{z^{q-j+1}} (1+z)^{n-j+k} \; dz
\\ = \frac{1}{2\pi i} 
\int_{|z|=\epsilon}  \frac{(1+z)^{n+k}}{z^{q+1}}
\sum_{j=0}^m {m+k\choose j} (-1)^j
\frac{z^j}{(1+z)^j} \; dz
\\ = \frac{1}{2\pi i} 
\int_{|z|=\epsilon}  \frac{(1+z)^{n+k}}{z^{q+1}}
\left(
\left(1-\frac{z}{1+z}\right)^{m+k}
-\sum_{j=m+1}^{m+k} 
{m+k\choose j} (-1)^j
\frac{z^j}{(1+z)^j}
\right) dz.$$
There are two pieces here inside the parentheses, call them $A$ and $B$.
For $A$ we get
$$\frac{1}{2\pi i} 
\int_{|z|=\epsilon}  \frac{(1+z)^{n+k}}{z^{q+1}}
\left(1-\frac{z}{1+z}\right)^{m+k} \; dz
\\ = \frac{1}{2\pi i} 
\int_{|z|=\epsilon}  \frac{1}{z^{q+1}}
\frac{1}{(1+z)^{m-n}} \; dz$$
This is the same  as the LHS. Now we just need  to show that piece $B$
is zero. It is given by
$$- \frac{1}{2\pi i} 
\int_{|z|=\epsilon}  \frac{(1+z)^{n+k}}{z^{q+1}}
\sum_{j=m+1}^{m+k} 
{m+k\choose j} (-1)^j
\frac{z^j}{(1+z)^j} \; dz.$$
But we have $j\ge m+1 = q+1$ so the apparent pole at zero vanishes and
this term is analytic in and  on the circle $|z|=\epsilon$ with no poles 
inside it and piece $B$ is indeed zero.

We can stop here without  further evaluation because the integrals for
LHS and RHS are seen to be the same. Moreover, they are trivial to evaluate,
we get $$(-1)^m \times {2m-n-1\choose m-n-1}.$$

The reader is invited to supply a proof for the case $q<m.$

A trace as to when this method appeared on MSE and by whom starts at this
MSE link.
</s>