1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ This looks similar to the first lemma here. math.stackexchange.com/questions/100299/… $\endgroup$ – Mauve Nov 27 '17 at 23:12
  • $\begingroup$ @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. $\endgroup$ – Shocky2 Nov 27 '17 at 23:18
3
$\begingroup$

Here is the proof.

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

$\endgroup$
  • $\begingroup$ I wish peace and abundance upon you! Thank you! $\endgroup$ – Shocky2 Nov 27 '17 at 23:33

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.