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}$$
 A: 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.
A: 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\le m$, $n\le m$ and $k\ge 0.$
We have by formal power series on the LHS
$$\sum_{j=0}^q {m\choose j} (-1)^j [z^{q-j}] (1+z)^{n-j}
= [z^q] \sum_{j=0}^q {m\choose j} (-1)^j z^j (1+z)^{n-j}.$$
Now we may  extend $j$ beyond $q$ because there  is no contribution to
the coefficient extractor in front:
$$[z^q] \sum_{j\ge 0} {m\choose j} (-1)^j z^j (1+z)^{n-j}
= [z^q] (1+z)^n \sum_{j\ge 0} {m\choose j} (-1)^j z^j (1+z)^{-j}
\\ = [z^q] (1+z)^n \left(1-\frac{z}{1+z}\right)^m
= [z^q] (1+z)^{n-m}.$$
Since we have $n\le m$ we write this as
$$[z^q] \frac{1}{(1+z)^{m-n}} = (-1)^q {m-n-1+q\choose m-n-1}.$$
Continuing with the RHS we get
$$\sum_{j=0}^q {m+k\choose j} (-1)^j [z^{q-j}] (1+z)^{n-j+k}
= [z^q] \sum_{j=0}^q {m+k\choose j} (-1)^j z^j (1+z)^{n-j+k}.$$
Once  more  we  may  extend  $j$   beyond  $q$  because  there  is  no
contribution to the coefficient extractor in front:
$$[z^q] \sum_{j\ge 0} {m+k\choose j} (-1)^j z^j (1+z)^{n-j+k}
= [z^q] (1+z)^{n+k} \sum_{j\ge 0} {m+k\choose j} (-1)^j z^j (1+z)^{-j}
\\ = [z^q] (1+z)^{n+k} \left(1-\frac{z}{1+z}\right)^{m+k}
= [z^q] (1+z)^{n-m}.$$
This is the same  as the LHS and we have the nice  result that the RHS
does not depend  on $k.$ Having seen this we  observe that it suffices
to evaluate the RHS, with the LHS being the special case $k=0.$
