# $\sum_{k=m}^{n}(-1)^k\binom{n}{k}\binom{k}{m}=0, n>m\geq 0$

I got quite some trouble trying to prove this. $$\sum_{k=m}^{n}(-1)^k\binom{n}{k}\binom{k}{m}=0, n>m\geq 0$$

I tried using $$\binom{n}{m}\binom{m}{k}=\binom{n}{k}\binom{n-k}{m-k}$$ and then changing the summation boundaries as $k=0, n=n-m$, but that took me nowhere... I would really appreciate help. Thank you.

• This looks similar to the first lemma here. math.stackexchange.com/questions/100299/… – Mauve Nov 27 '17 at 23:12
• @AirConditioner Thank you for a useful post! It is actually the same thing! But, I would really appreciate it if you wrote a proof for it, so I can accept it as the answer... In the said post a few steps are skipped, which I don't really know how to do. – Shocky2 Nov 27 '17 at 23:18

\begin{align} \sum_{k=m}^{n}(-1)^k\binom{n}{k}\binom{k}{m} &= \sum_{k=m}^{n}(-1)^k \frac{n!}{k!(n-k)!}\frac{k!}{(k-m)!m!} \\ &= \sum_{k=m}^{n}(-1)^k \frac{n!}{(n-m)!m!}\frac{(n-m)!}{(n-k)!(k-m)!} \\ &= \sum_{k=m}^{n}(-1)^k \binom{n}{m}\binom{n-m}{k-m} \\ &= \binom{n}{m} \sum_{k=m}^{n}(-1)^k \binom{n-m}{k-m} \\ &= (-1)^m \binom{n}{m} \sum_{j=0}^{n-m} \binom{n-m}{j}(-1)^{j}(1)^{n-m-j} \\ &= (-1)^m \binom{n}{m} (1-1)^{n-m} = 0. \end{align} Note that in the fifth equality, I set $j = k -m$ and used $(-1)^{j+m} = (-1)^j(-1)^m$.