# proof with double counting

Using double counting (and without algebraic calculations), prove that $$\sum_{k=r}^n \binom n k \binom k r = 2^{n-r} \binom{n}{n-r}.$$

This question was assigned to me on a quiz and I was not able to do it. Our math teacher thought "counting" is important to discrete math so he added this as an additional thing to the course's curriculmn and there is no textbook notes on counting. The notes he has written make no sense to me and so I don't understand them. Can someone please explain me how this proof works as in what is going on and what is counting? the $\binom{n}{k}$ formula looks a lot like this formula I did long ago in statistics class with combinations other than that nothing else is familiar to me.

-
Certainly combinatorial problems of this sort are a big part of discrete mathematics. There are many books on this at various levels. – Michael Hardy Mar 12 '12 at 3:06

$\binom{n}{k}$ counts the number of ways in which you can select $k$ items from a collection of $n$ items.

Generally speaking, when you multiply two counts, you are counting the number of ways in which the two selections can be carried out; when you add them, you are counting the number of ways in which one of two selections can be carried out. For instance, if you have 3 pants and 4 shirts, then you have $3\times 4$ ways of selecting what pair of pants and shirt to wear; if you have 3 routes you can take by car to get to school and 4 routes you can take by bike, then you have $3+4$ routes you can take to get to school by either car or bike.

The binomial coefficient on the right hand side, $\binom{n}{n-r}$, counts the number of ways in which you can select $n-r$ items from $n$ possibilities; note that this is the same as $\binom{n}{r}$, the number of ways of selecting $r$ items from $n$ possibilities: because selecting the $n-r$ that you want is equivalent to selecting the $r$ that you don't want.

So the right hand side counts the number of ways of selecting $r$ items from $n$ possibilities, $2^{n-r}$ times.

Let's look at the sum on the left hand side: the $k$th summand is $$\binom{n}{k}\binom{k}{r}.$$ The first factor counts the number of ways of selecting $k$ items from $n$ possibilities; the second factor counts the number of ways of selecting $r$ items from $k$ items.

One possible interpretation is: you have $n$ things; first you select $k$ of them, and then you select $r$ items from the $k$ you selected in the first place. That is, you can think of the factor $\binom{n}{k}$ as a first-step "culling" of the possibilities, and the second factor $\binom{k}{r}$ as the final selection process.

Note, however, that the number of ways of selecting $r$ times this way is not the same as the number of ways of selecting $r$ items. For instance, if $n=3$, $r=1$, and $k=2$, then you are trying to pick a single element from $\{1,2,3\}$; there are three ways of doing this (pick $1$, pick $2$, or pick $3$); but if you first pick two items and then you pick one, then there are two ways you can end up picking $1$ (first pick $1$ and $2$, then pick $1$; or first pick $1$ and $3$, then pick $1$), two ways you can end up picking $2$, and two ways you can end up picking $3$. So you end up with $6$ different ways, instead of $3$ possible outcomes...

Now, by adding all of these procedures from $k=r$ to $k=n$, what are you doing? You are counting the number of ways of taking a $2$-step process to select $r$ items: you could first select $r$ items, and then keep them ($k=r$); or you could first select $r+1$ items and then pick $r$ of them ($k=r+1$); or you can first select $r+2$ items, and then pick $r$ of them ($k=r+2$); ...; or you could just pick all $n$ items and then select $r$ of them ($k=n$).

So the left hand side is counting the total number of ways in which you can select $r$ items from $n$ possibilities in a $2$-step selecting procedure.

The right hand side is counting the number of ways of selecting $r$ items from $n$ possibilities, and then multiplying that by $2^{n-r}$.

That suggests trying to figure out whether the $2$-step selecting procedure will result in the same $r$ items being chosen exactly $2^{n-r}$ times.

In my example with $n=3$ and $r=1$, we have 1 way in which $1$ will be ultimately chosen if we first select just $1$ and then keep it ($k=r$); we have two ways in which $1$ will ultimately be chosen if we first select two items, which includes $1$, and then select $1$ ($k=r+1=2$, the case we figured out above); and there is one way in which we will ultimately choose $1$ if we first keep all three items and then select $1$. That's a total of $1+2+1= 4 = 2^{3-1}$ ways of ultimately ending with $1$, so the formula works out.

Try to see if you can show that you will always have exactly $2^{n-r}$ ways of ending with a particular selection of $r$ items through the $2$-step procedure. If you do, then that will establish the equality, because both sides of the equality are counting the same thing, in two different ways.

-
Just to make this proof complete: Let’s take a fixed $r$-element subset $R$ of the $n$-element set $N$. How many times is $R$ selected in the 2-step procedure? As many times as ways of selecting $k$-element set $K$, such that $R ⊆ K ⊆ N$. When looking on indicator function of $K$, we notice elements of $R$ produce 1, other $n-r$ elements are unrestricted. There are 2 possible values for each of them, ergo using the multiplication principle stated above we conclude $2^{n-r}$ is the answer. – Palec Dec 14 '13 at 2:56