An archived instance of a Discrete forum

A binomial identity

mark

Consider the identity

k{n\choose k} = n{n-1 \choose k-1}.
  1. Write down an algebraic proof of this identity
  2. Write down a combinatorial proof of the identity.
ksimmon1
  1. I think I got the algebraic proof:
k{n\choose k} = n{n-1 \choose k-1}
k({\frac{n!}{k!(n-k)!}}) = n({\frac{(n-1)!}{(n-1-(k-1))!}})
\frac{kn!}{k!(n-k)!} = \frac{n(n-1)!}{(k-1)!(n-1-k+1)!}
\frac{kn!}{k!(n-k)!} = \frac{n!}{(k-1)!(n-k)!}
\frac{n!}{(k-1)!(n-k)!} = \frac{n!}{(k-1)!(n-k)!}
  1. I am struggling to get the combinatorial proof.

I plugged in values and can understand how they get the same answer. I just am struggling to write the proof.

mark

Here is a way to think about the combinatorial proof. Suppose we want to pick a subset of size k from a larger set of size n with a distinguished member of the subset. As a real world example, perhaps we want to pick a committee from all the faculty at a university and we need a chairperson of the committee. Here are two ways to do this:

First, pick the committee, then pick the chairperson. Since there are k people on the committee and n people total, there are

n\choose k

ways to pick the committee. Once the committee is chosen, there are k ways to pick the chairperson. That results in a total of

k {n\choose k}

ways to select the committee with chair.

Alternatively, what if you first pick the chair and then pick the remaining members of the committee? How many choices for the chair do you have and how many choices for the remaining members of the committee do you have?

ksimmon1

Thank you, putting it in those terms it makes much more sense.

If we chose the chair first out of n people. There would be n different ways to choose the chairperson. Then to pick the rest of the remaining committee it would be out of n-1 people (subtracting the chairperson from the total pool) and k-1 people on the committee (subtracting one again for the chairperson out of the total count of the committee). This would leave us with:

n{n-1 \choose\ {k-1}}

This would mean that:

k{n\choose k} = n{n-1 \choose k-1}