Use combinatorial proof to show that $\sum\limits_{k=0}^{n}\binom{n}{k}\binom{k}{m}=\binom{n}{m}2^{n-m}$.

Question

I am going through a self-teaching journey in mathematics. Right now I am reading Book of Proof, by Richard Hammack, and in the Chapter on Counting, I came across the following exercise:

Use combinatorial proof to show that $\sum\limits_{k=0}^{n}\binom{n}{k}\binom{k}{m}=\binom{n}{m}2^{n-m}$.

My proof was the following:

Notice that the right-hand side of the equation is the number of ways we can make a string of length $n$ from the symbols $\{A,B,C\}$ with repetition allowed. First we choose the position of the $A$'s. We can do that in $\binom{n}{m}$ ways, such that $m\leq n$ is the number of $A$'s in our string. For the remaining $(n-m)$ positions, we have two options: they are either $B$ or $C$, therefore there are $2^{n-m}$ ways of filling them up. Thus, as we claimed, $\binom{n}{m}2^{n-m}$.

Now we will count the number of ways we can make a string of length $n$ from the symbols $\{A,B,C\}$ with repetition allowed in a different way: first, we select the number of positions that are not $C$, and fill the rest with $C$'s. We can do this in $\binom{n}{k}$ ways, where $k$ is the number of positions that are not $C$. From those $k$ positions, we choose the ones that are $A$'s and fill them up, which we can do in $\binom{k}{m}$ ways, where $m$ is the number of $A$'s in our string. Finally, fill every blank space with $B$'s. Thus, the number of string with $(n-k)$ $C$'s and $m$ $A$'s is $\binom{n}{k}\binom{k}{m}$. Since $k$ can be any number in $[0,n]$, to count all the possible strings we have $\sum_{k=0}^{n}\binom{n}{k}\binom{k}{m}$.

Since the right-hand and the left-hand sides are solutions to the same counting problem, we conclude they are equal.$\blacksquare$

I desperately need some feedback on my proof-writing skills. It feels like my argument is solid, but at the same time, my writing might be somewhat convoluted. I don't know if it is clear enough, not straightforward enough, or if I explained too much. How detailed should I be?

Feel free to be very critical. I wanna be able to write proofs acceptably.

Answer 1

Notice that the right-hand side of the equation is the number of ways we can make a string of length n from the symbols {A,B,C} with repetition allowed. First we choose the position of the A's.

You are actually counting ways to build a length $n$ string of exactly $m$ letter A, and some combination of B, and C.

However, your argument is valid, if a little verbose.

---

So, indeed, where the items mentioned below may be interpreted as 'positions for the letters' we have:

• $\binom{n}{m}$ counts the number of ways to select $m$ items from a set of $n$.

• and $2^{n-m}$ counts the subsets of a set of size $n-m$. (That is, the count of choices made to place each item from a set of $n-m$ into one or the other of two subsets.)

• Together then, $\binom{n}{m}2^{n-m}$ counts all ways to partition a set of $n$ items into a set of $m$ items, a set of any size $k$ in $[[1..n-m]]$, and a remaining set.

• Meanwhile $\sum_{k=0}^{n-m}\binom{n}{k}\binom{n-k}{m}$ is the count of all ways to partition a set of $n$ items into a set of any size $k$ in $[[1..n-m]]$, a set of size $m$, and a remaining set.

• Therefore these counts are equal: $$\dbinom nm2^{n-m}=\sum_{k=0}^{n-m}\dbinom nk\dbinom {n-k}m$$

Answer 2

Similar to your other posting, I think that your proof is well written and valid. In this case, my sole (very minor) criticism is that when you were describing the RHS, it was not immediately clear that you intended that there will always be exactly $(m)$ A's.

After a couple of sentences, I was able to reverse engineer that this was your intent.

---

Moderately off topic, I think that your approach was very creative. I would have taken a much more pedestrian approach that still represented a combinatoric proof.

I would have said that the RHS represents overcounting each distinct subset of $m$ items, selected without replacement from the superset of $n$ items. Also, the overcounting is such that each pertinent subset is counted exactly $2^{n-m}$ times.

Therefore, the challenge would be to show that the LHS has similar overcounting.

On the LHS attention can be confined to those values of $k$ that are $\geq m$. Then, with respect to that particular value of $k$, each individual subset represented on the RHS will be counted (on the LHS, for this value of $k$) a total of $~\displaystyle \binom{n-m}{k-m}~$ times.

That is, with respect to a specific subset of $m$ items, on the LHS, you are only interested in those $k$ items that are a superset to the $m$ items. There will be exactly $~\displaystyle \binom{n-m}{k-m}~$ such pertinent supersets, for one individual subset of $m$ items.

Therefore, the problem has been reduced to showing that (in general)

$$\sum_{k=m}^n \binom{n-m}{k-m} = 2^{n-m}. \tag1 $$

This can be done by re-indexing (1) above into

$$\sum_{k=0}^{n-m} \binom{n-m}{k}. \tag2 $$

(2) above is easily seen to be true from the binomial expansion of $~\displaystyle 2^{n-m} = (1 + 1)^{n-m}.$