Proving an identity involving the alternating sum of products of binomial coefficients Prove the following identity:
$$
\sum_{k\ =\ 0}^{{\large\ell}}\left(-1\right)^{k}
\binom{j - k}{\ell - 1}\binom{\ell}{k} = 0
$$
for some integers $\ell \geq 1$ and $j\geq \ell$.
Using wolfram alpha I have confirmed that this identity is true. But I am not sure how I can prove it myself. I have tried to split it into even and odd values of $k$, but that did not work. I have tried a proof by induction in combination with the identity $\binom{n}{k}=\binom{n-1}{k}+\binom{n-1}{k-1}$, but that also did not work. I think the proof might require a more sophisticated method.
 A: Here is a combinatorial proof. Consider this question:

How many subsets of the $\{1,2,\dots,j\}$ of size $l-1$ contain all of the numbers $\{1,2,\dots,l\}$? 

Obviously, the answer is zero, because there are more than $l-1$ numbers in $\{1,2,\dots,l\}$!
On the other hand, we can count this using the principle of inclusion exclusion. Take all $\binom{j}{l-1}$ subsets of size $l-1$, then for each element $h$ of $\{1,2,\dots,l\}$, subtract $\binom{j-1}{l-1}$ subsets which are missing $h$. Then add back in the doubly subtracted subsets, subtract the triply subtracted subsets, etc. The result is exactly your binomial sum.
A: Your induction idea should work.  Using the identity you suggested, rewrite your expression as
$$
\begin{align}
\sum_{k=0}^l(-1)^k\binom{j-k}{l-1}\binom{l}{k}&=\sum_{k=0}^{l-1}(-1)^k\binom{j-k}{l-1}\binom{l-1}{k}+\sum_{k=1}^l(-1)^k\binom{j-k}{l-1}\binom{l-1}{k-1}\\
&=\sum_{k=0}^{l-1}(-1)^k\binom{j-k}{l-1}\binom{l-1}{k}-\sum_{k=0}^{l-1}(-1)^k\binom{j-1-k}{l-1}\binom{l-1}{k}.
\end{align}
$$
Now use your identity a second time, applying it to the binomial coefficient $\binom{j-k}{l-1}$ in the first sum.  After cancelling some terms, you will be able to apply induction on $l$.
A: We may write
$$\sum_{k=0}^\ell {\ell\choose k} (-1)^k {j-k\choose \ell-1}
= \sum_{k=0}^\ell {\ell\choose k} (-1)^k
[z^{\ell-1}] (1+z)^{j-k}
\\ = [z^{\ell-1}] (1+z)^j
\sum_{k=0}^\ell {\ell\choose k} (-1)^k  (1+z)^{-k}
= [z^{\ell-1}] (1+z)^j  
\left(1-\frac{1}{1+z}\right)^\ell
\\ = [z^{\ell-1}] (1+z)^{j-\ell} z^\ell.$$
We have in any case that  $z^\ell (1+z)^{j-\ell} = z^\ell + \cdots$ so
this term  starts one  power beyond the  coefficient extractor  and is
indeed equal to zero.
