Proving an identity involving the alternating sum of products of binomial coefficients

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.


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