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

Prove the following identity: $$\sum_{k=0}^{l}(-1)^k \binom{j-k}{l-1}\binom{l}{k}=0$$ for some integers $$l\geq1$$ and $$j\geq l$$.

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.

## 3 Answers

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

• Ok, working through as you say: The induction hypothesis is $$\sum_{k=0}^{l-1}(-1)^k\binom{j-k}{l-2}\binom{l-1}{k}=0~.$$ After applying the identity for the second time, as you directed, we have \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-1}{l-2}\binom{l-1}{k}\\ &=\sum_{k=0}^{l-1}(-1)^k\binom{j-k}{l-2}\binom{l-1}{k}\frac{j-k-l+2}{j-k}\\ &=-(l-2)\sum_{k=0}^{l-1}(-1)^k\binom{j-k}{l-2}\binom{l-1}{k}\frac{1}{j-k}~. \end{align} In the last line I have used the induction hypothesis. But I don't see where to go from here. – NormalsNotFar Feb 11 at 14:00
• The induction hypothesis is that the statement holds for all $j\ge l-1$. So you can apply it in your first line. – Will Orrick Feb 11 at 14:07
• Ahhh, that's the piece of information that I've been missing. Much appreciated! – NormalsNotFar Feb 11 at 14:22

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.

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.