Mfrhtyj

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}$$

This can be done using a basic complex variables technique.
Suppose we seek to verify that
$$sum_{j=0}^q {mchoose j} (-1)^j {n-jchoose q-j}
= sum_{j=0}^q {m+kchoose j} (-1)^j {n-j+kchoose q-j} .$$
We will treat the case $q=m$ and $nle m.$

Introduce the two integral representations
$${n-jchoose q-j}
= frac{1}{2pi i}
int_{|z|=epsilon} frac{1}{z^{q-j+1}} (1+z)^{n-j} ; dz$$
and
$${n-j+kchoose q-j}
= frac{1}{2pi 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}{2pi i}
int_{|z|=epsilon}
sum_{j=0}^m {mchoose j} (-1)^j
frac{1}{z^{q-j+1}} (1+z)^{n-j} ; dz
\ = frac{1}{2pi i}
int_{|z|=epsilon}
frac{(1+z)^n}{z^{q+1}}
sum_{j=0}^m {mchoose j} (-1)^j
frac{z^j}{(1+z)^j} ; dz
\ = frac{1}{2pi i}
int_{|z|=epsilon}
frac{(1+z)^n}{z^{q+1}}
left(1-frac{z}{1+z}right)^m ; dz
\ = frac{1}{2pi 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}{2pi i}
int_{|z|=epsilon}
sum_{j=0}^m {m+kchoose j} (-1)^j
frac{1}{z^{q-j+1}} (1+z)^{n-j+k} ; dz
\ = frac{1}{2pi i}
int_{|z|=epsilon} frac{(1+z)^{n+k}}{z^{q+1}}
sum_{j=0}^m {m+kchoose j} (-1)^j
frac{z^j}{(1+z)^j} ; dz
\ = frac{1}{2pi 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+kchoose 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}{2pi i}
int_{|z|=epsilon} frac{(1+z)^{n+k}}{z^{q+1}}
left(1-frac{z}{1+z}right)^{m+k} ; dz
\ = frac{1}{2pi 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}{2pi i}
int_{|z|=epsilon} frac{(1+z)^{n+k}}{z^{q+1}}
sum_{j=m+1}^{m+k}
{m+kchoose j} (-1)^j
frac{z^j}{(1+z)^j} ; dz.$$

But we have $jge 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-1choose 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.

Suppose we seek to verify that
$$sum_{j=0}^q {mchoose j} (-1)^j {n-jchoose q-j}
= sum_{j=0}^q {m+kchoose j} (-1)^j {n-j+kchoose q-j} .$$

We will treat the case $qle m$, $nle m$ and $kge 0.$
We have by formal power series on the LHS

$$sum_{j=0}^q {mchoose j} (-1)^j [z^{q-j}] (1+z)^{n-j}
= [z^q] sum_{j=0}^q {mchoose 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_{jge 0} {mchoose j} (-1)^j z^j (1+z)^{n-j}
= [z^q] (1+z)^n sum_{jge 0} {mchoose 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 $nle m$ we write this as

$$[z^q] frac{1}{(1+z)^{m-n}} = (-1)^q {m-n-1+qchoose m-n-1}.$$

Continuing with the RHS we get

$$sum_{j=0}^q {m+kchoose j} (-1)^j [z^{q-j}] (1+z)^{n-j+k}
= [z^q] sum_{j=0}^q {m+kchoose 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_{jge 0} {m+kchoose j} (-1)^j z^j (1+z)^{n-j+k}
= [z^q] (1+z)^{n+k} sum_{jge 0} {m+kchoose 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.$