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

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

• 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. Commented Feb 11, 2019 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. Commented Feb 11, 2019 at 14:07
• Ahhh, that's the piece of information that I've been missing. Much appreciated! Commented Feb 11, 2019 at 14:22
• @Will Orrick I'm sure I'm missing something here, but if the statement is true for $j \geq l-1$, then isn't it automatically true for $j \geq l$ since $l$ is greater than $l-1$? I know this is a couple of years later, but any help you can give would be appreciated. Commented Feb 24, 2021 at 16:08
• @flevinBombastus This identity has two parameters, $l$ and $j$, and we want to prove that it holds for all $l\ge1$ and all $j\ge l$. The induction hypothesis is that it holds for $l=L-1$ for all $j\ge L-1$. This hypothesis immediately implies it holds for all $j\ge L$ when $l=L-1$, but we must still prove the it holds for all $j\ge L$ when $l=L$. Commented Feb 24, 2021 at 16:31

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.