Identity with an alternating binomial sum: $\sum\limits_{i=1}^n(-1)^i{n-i \choose n-k} {k \choose i} = {n-k\choose k}$

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.

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