I'm learning for the test and:

Prove identity: $$\sum_{i=1}^n(-1)^i{n-i \choose n-k} {k \choose i} = {n-k\choose k}$$ for all $n,k\in \mathbb{N}$.

This problem is just awful. I was trying to solve it for the last three hours and finally it has defeated me, so I'm writing for help. I think combinatorial proof is not possible because of $(-1)$ factor, which we can get rid of since: $(-1)^i {x\choose i}={i-1-x\choose i}$ but then we have negative upper number in binomial which is not good for interpretation. So I tried with generating functions but it also lead me to nowhere :(


Hints: For the $\dbinom{n-i}{n-k}$ I prefer the equivalent $\dbinom{n-i}{k-i}$.

As mentioned in the OP, the minus signs perhaps discourage most combinatorial interpretation. However, they are familiar in one combinatorial setting, Inclusion/Exclusion.

We have $n$ apples, of which $k$ are bad. We find the number of ways to choose $k$ good apples. Of course this is $\dbinom{n-k}{k}$. But let us count it another way.

We will do it by Inclusion/Exclusion. Our first estimate ($i=0$) is $\binom{n-0}{k-0}\binom{k}{0}$, a fancy way of saying we choose $k$ from the $n$.

This is wrong, we need to subtract all choices where there was a bad apple. As a first estimate of that, choose the bad apple (there are $\binom{k}{1}$ ways to do it, and for each choice, $\binom{n-1}{k-1}$ to choose the rest.

But we have subtracted too much. Continue.

  • $\begingroup$ This is just brilliant, thank you so much! $\endgroup$ – xan Jun 15 '13 at 19:27

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.