3
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – NormalsNotFar Feb 11 at 14:00
  • $\begingroup$ The induction hypothesis is that the statement holds for all $j\ge l-1$. So you can apply it in your first line. $\endgroup$ – Will Orrick Feb 11 at 14:07
  • $\begingroup$ Ahhh, that's the piece of information that I've been missing. Much appreciated! $\endgroup$ – NormalsNotFar Feb 11 at 14:22
2
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.