Proving $\sum_{k=m}^n\binom nk\binom km=2^{n-m}\binom nm$ [duplicate]

Question

$$\sum_{k=m}^n{n\choose k}{k \choose m}=2^{n-m}{n\choose m}$$

I proved this by considering $2^{n-m}=(1+1)^{n-m}$ in the RHS, expanding it into binomials, and then doing some manipulations with the factorials.

It's also possible to transform the LHS product and take one binomial coefficient out of the sum.

The LHS is clear. It seems like we are counting all sub-subsets of size $m$, i.e. take an element from the initial powerset whose cardinality is at least $m$, then count its subsets that are exactly $m$ in size.

For the RHS, we are considering the sub-subet first, i.e. the $n\choose m$, then associating it with the possible subsets barring the selected elements, i.e., the remaining $2^{n-m}$.

However, I don't see how I can connect these two intuitive explanations in a word proof (connect them with respect to "$=$"). The two aforementioned algebraical manipulations offer no insight. So I am not sure how I should explain this in the assignment.

Answer 1

Here's a combinatorial argument:

Suppose we have $n$ people and want to form a 'group' with at least $m$ people and exactly $m$ 'leaders'. So we want to count how many ways we can do it.

One way to count it is to first select the 'leaders', which can be done in $n\choose m$ ways, and then each of the $n-m$ remaining people might or not be in the 'group', so there are $2^{n-m}$ ways to complete the group. Therefore, there are $$2^{n-m} {n\choose m}$$ distinct forms to do the desired.

On the other hand, suppose $k\geq m$. We would like to count how many groups there are with exactly $k$ people and $m$ leaders. We can choose first the members of the group (which can be done in $n\choose k$ ways) and then choose the $m$ leaders out of the $k$ people selected (which can be done in $k\choose m$ ways). Thus, there are ${n\choose k} {k\choose m}$ groups with exactly $k$ people and $m$ leaders. Therefore, the total number of groups we can form is $$\sum_{k=m}^n{n\choose k}{k \choose m}.$$

Answer 2

Using the product identitity ${n \choose k} {k \choose m} = {n \choose m}{n-m \choose k-m}$

which can be proven by direct comparison or by combinatorial argument (how to choose $m$ balls for box $1$ and $k-m$ balls for box $2$, either you take every ball and then choose which balls go for box $1$ or you choose ball for box $1$ from the total set and then the $k-m$ balls also form total set)

Thus $$ \sum_{k=m}^n {n \choose k} {k \choose m} = \sum_{k=m}^n {n \choose m}{n-m \choose k-m} \overset{j=k-m}{=} {n \choose m} \sum_{j=0}^{n-m} {n-m \choose j} = {n \choose m} 2^{m-n} $$

Answer 3

A direct algebraic proof: \begin{align*} \sum_{k=m}^n{n\choose k}{k \choose m} &=\sum_{k=m}^n\frac{n!}{k!(n-k)!}\cdot\frac{k!}{m!(k-m)!} =\frac{n!}{m!}\sum_{k=m}^n\frac{1}{(n-k)!(k-m)!} \\ &=\frac{n!}{m!}\sum_{i=0}^{n-m}\frac{1}{(n-(m+i))!i!} =\frac{n!}{m!(n-m)!}\sum_{i=0}^{n-m}{n-m\choose i} \\ &=\frac{n!}{m!(n-m)!}(1+1)^{n-m} =2^{n-m}{n\choose m} \end{align*} where $k=m+i$.

A probabilistic proof: suppose $X_1,\dots,X_n\in\{0,1\}$ are the results of independent fair coin tossing, so that $X_i$s are iid Bernoulli(1/2). Let $Z$ be the number of subsets of $\{X_1,\dots,X_n\}$ of size $m$ whose all elements are zero; e.g. if $n=4$, $m=2$, $X=\{0,0,1,0\}$ then these subsets are $\{X_1,X_2\}$,$\{X_1,X_4\}$,$\{X_2,X_4\}$; there are three of them. Then the direct calculation gives $$ \mathbb{E}(Z)={n\choose m} 2^{-m} $$ as for each subset of size $m$ the probabiliy to have only zeroes is $2^{-m}$.

On the other hand, each configuration of $X_1,\dots,X_n$ has the probability $2^{-n}$. For each configurations which has $k\ge m$ zeros, there are ${k\choose m}$ subsets which are included in $Z$. Hence $$ \mathbb{E}(Z\mid A_k)={k\choose m} $$ where $$ A_k=\{\text{there are exactly $k$ zeros amongst $X_1,\dots,X_n$}\} $$ and $$ \mathbb{P}(A_k)={n\choose k}2^{-n} $$ Now the law of iterated expectations $\mathbb{E}(Z)=\sum_k \mathbb{E}(Z\mid A_k)\mathbb{P}(A_k)$ gives the result.