how to calculate $\sum^{n}_{k=m}\binom{k}{m}\binom{n}{k}$?

Question

For natural numbers $m \leq n$ calculate (i.e. express by a simple formula not containing a sum) $$\sum^{n}_{k=m}\binom{k}{m}\binom{n}{k}.$$

I searched and answer is probably

$=\binom{n}{m}\sum^{n}_{k=m}\binom{n-m}{n-k}$

$=\binom{n}{m}\sum^{n-m}_{k=0}\binom{n-m}{k}$

$=\binom{n}{m}2^{n-m}$

Q

1: Is the answer correct?

2: Why take $\binom{n}{m}$ in front of sum?

3: How to transform the first formula to become second formula?

Answer 1

$$\binom{k}m\binom{n}k=\frac{k!}{m!(k-m)!}\frac{n!}{k!(n-k)!}=\frac{n!}{m!(k-m)!(n-k)!}=$$$$\frac{n!(n-m)!}{m!(n-m)!(k-m)!(n-k)!}=\binom{n}{m}\binom{n-m}{n-k}$$

$\binom{n}{m}$ can be taken in front because it does not depend on index $k$.

Answer 2

It is sufficient to answer (3).

We obtain for integral $0\leq m\leq n$: \begin{align*} \color{blue}{\sum_{k=m}^n\binom{k}{m}\binom{n}{k}}&=\sum_{k=m}^n\binom{n}{m}\binom{n-m}{n-k}\tag{1}\\ &=\binom{n}{m}\sum_{k=m}^n\binom{n-m}{n-k}\tag{2}\\ &=\binom{n}{m}\sum_{k=0}^{n-m}\binom{n-m}{n-(k+m)}\tag{3}\\ &=\binom{n}{m}\sum_{k=0}^{n-m}\binom{n-m}{k}\tag{4}\\ &=\binom{n}{m}\sum_{k=0}^{n-m}\binom{n-m}{k}1^k1^{n-m-k}\\ &=\binom{n}{m}(1+1)^{n-m}\tag{5}\\ &\,\,\color{blue}{=\binom{n}{m}2^{n-m}} \end{align*} and the claim follows.

Comment:

• In (1) we use the binomial identity $\binom{k}{m}\binom{n}{k}=\binom{n}{m}\binom{n-m}{n-k}$.

• In (2) we factor out $\binom{n}{m}$ which does not depend on the index $k$.

• In (3) we shift the index to start with $k=0$. To compensate the index-shift $k\to k-m$ we replace in the summand $k$ with $k+m$.

• In (4) we use the binomial identity $\binom{p}{q}=\binom{p}{p-q}$.

• In (5) we apply the binomial theorem.