Strategy: Committee Forming

One way in which we can prove combinatorial identities is through "Committee Forming". In order to get an idea of what this really means, let us look at some examples!

Prove that $$n\binom{n-1}{r-1} = r\binom{n}{r}.$$

Well, we can use our so called "committee forming" in order to prove this identity. Suppose that we have $n$ people and we are trying to choose a committee of size $r$ with a president.

We could initially choose the president in $n$ different ways. Then, we can choose the other $r-1$ people from the remaining $n-1$. This is equivalent to $n\binom{n-1}{r-1}$ ways. This is our left hand side!

Now, let's see our right hand side. Well, we can choose the committee in $\binom{n}{r}$ ways. Now we just have to choose one of the members of the committee to be the president. This can be done in $r$ ways. So this is equivalent to $r\binom{n}{r}$ ways. Hey! This is our right hand side!

So therefore, with this committee forming argument, we have proved the expression.

Prove that $$\binom{n}{k} \binom{k}{m} = \binom{n}{m} \binom{n-m}{k-m}.$$

Well, consider a pool of $n$ people to choose from. We want to form a committee of size $k$ and then from those people, we want to form a subcommittee of size $m$. In the left hand side, we are doing exactly that.

However on the right hand side, we are choosing the subcommittee of size first $m$. Only after that are we choosing the remaining people to be in the committee of $m$. Notice that we can't choose any of the $m$ people already, so there are $n-m$ people to choose from. Now notice that we only have to choose $k-m$ more members since every member of the subcommittee is a member of the committee. This is equivalent to the right hand side!

So we are counting the same thing in two different ways! Remember if you ever get stuck in proving one of these combinatorial identities, think to yourself: How do the left hand side and right hand side count the same thing?

Prove Vandermonde's Identity which states that: $$\sum_{k=0}^r \binom{m}{k} \binom{n}{r-k} = \binom{m+n}{r}.$$

Well, this looks like kind of a mess! However, realize that we are adding a bunch of things together. When we do this, this often suggests that there are different cases to consider.

So suppose that we have a pool of $m$ people and another pool of $n$ people. Among them we want to choose an $r$ person committee. Alright, so this has the right side covered.

Now, we could take $0$ people from the $m$-sized pool and $r$ people from the $n$-sized pool...$1$ person from the $m$-sized pool and $r-1$ from the $n$-sized pool .....$2$ people and $r-2$ people..... all the way to $r$ people from the $m$-sized pool and $0$ people from the $n$-sized pool. Note that the left hand side sums up all of these individual cases!

So, we have proved this identity!

This method is a neat way to prove many of these combinatorial identities. It can be especially fruitful when the algebra is really messy. Happy solving!