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

Question

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.

Answer 1

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

Answer 2

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.

Answer 3

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.