1

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?

user
  • 26,272
volvosatoh
  • 23
  • Combinatorial interpretation: You have n ppl and you need to form a committee. The committee needs to have m board members. We can either first pick the committee members and then pick the board members out of them which gives you the sum. Alternatively, you can pick the board members first, which gives $\binom{n}m$. Then the rest of the committee comes from the n-m people, of which there are $2^{n-m}$ choices. – Sandeep Silwal Jun 23 '19 at 14:49

2 Answers2

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.

Markus Scheuer
  • 108,315
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$.

drhab
  • 151,093
  • I understood. And why can $\sum^{n}{k=m}$ transform $\sum^{n-m}{k=0}$ ? – volvosatoh Jun 23 '19 at 14:23
  • 1
    $\binom{n-m}{n-m}+\cdots+\binom{n-m}0=\binom{n-m}0+\cdots+\binom{n-m}{n-m}$. – drhab Jun 23 '19 at 14:28
  • if so why $\binom{n-m}{n-k}$ transform $\binom{n-m}{k}$ ? – volvosatoh Jun 23 '19 at 14:36
  • Those expression are not equal (and nobody says they are) – drhab Jun 23 '19 at 15:01
  • so is $\sum^{n}{k=m}\binom{n-m}{n-k}$ = $\sum^{n-m}{k=0}\binom{n-m}{k}$ wrong ? – volvosatoh Jun 23 '19 at 15:10
  • No, it is correct, but does not rest on equality of the expressions mentioned in your former comment. – drhab Jun 23 '19 at 15:17
  • I'm sorry, my writing might have confused you. What I meant to was why $\sum^{n}{k=m}\binom{n-m}{n-k}$ transform $\sum^{n-m}{k=0}\binom{n-m}{k}$. – volvosatoh Jun 23 '19 at 15:25
  • I already answered that in my first comment. Do you agree that $\sum_{k=m}^{n}\binom{n-m}{n-k}=\binom{n-m}{n-m}+\cdots+\binom{n-m}{0}$ and that$\sum_{k=0}^{n-m}\binom{n-m}{k}=\binom{n-m}{0}+\cdots+\binom{n-m}{n-m}$ so that the expressions are equal? The second expression is on its turn equal to $\sum_{k=0}^{n-m}\binom{n-m}{k}1^{k}1^{n-m-k}=2^{n-m}$. – drhab Jun 23 '19 at 19:00
  • I understand. Thank you for your explanation. – volvosatoh Jun 24 '19 at 00:49
  • You are welcome. – drhab Jun 24 '19 at 06:13