Combinatorial proof of $ k{n \choose k} = n {n-1\choose k-1} $

Question

I have to prove this using a combinatorial proof

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

What's the standard procedure on doing this? The only thing I managed was to split it into: (by fixing one element) $$ k{n \choose k} = k\bigg[ {n-1 \choose k} {n-1\choose k-1}\bigg]$$

But does this help? Or how do I go from here?

Answer 1

A combinatorial proof is generally done by finding one problem and solving it in two different ways. The results will look different, but since they're solutions to the same problem they must be the same.

For this problem I thought of picking a soccer team with $k$ players (one of which is captain) out of $n$ candidates, and here are two ways to find the number of ways to do that.

1. Pick a team of $k$ players. This can be done in $n \choose k$ ways. And then make one of them captain, since there are $k$ players, this can be done in $k$ ways and you get $k{n\choose k}$ possible teams.

2. Pick a captain. There are $n$ candidates so this can be done in $n$ ways. Then pick the last $k-1$ players from the remaining $n-1$ candidates. There are $n-1 \choose k-1$ ways to do that, giving you a total of $n{n-1\choose k-1}$ possible teams.

And now you can see that both sides of the equation are solutions to the same counting problem, so they must be equal.

Answer 2

Well, it is rather $\displaystyle k{n \choose k} = k\bigg[ {n-1 \choose k} + {n-1\choose k-1}\bigg]$, and it seems promising: $${n-1\choose k} = \frac{n-k}k{n-1\choose k-1}$$ and with it you can finish the proof.

By the way, both sides are counting (for example) the pointed subsets of $k$ members in a base set of $n$ members. The left hand side first picks the group of $k$ members then its 'head', the point. The right hand side first picks an arbitrary member then the remaining group of $k-1$ members from the $n-1$ others.

Answer 3

There is no uniform procedure as such.

In this case, though, a fairly straightforward approach works. Let's start on the left. We want to find a counting problem whose answer is $k \binom nk$. Maybe we don't see how to do that. Let's take a piece of it, then: find a counting problem whose answer is $\binom nk$. That's easy — the process is picking $k$ objects from $n$ objects. Now, what about that $k$? It's multiplied onto the $\binom nk$, so maybe it's an instance of the Rule of Product:

Choose $k$ objects out of $n$ objects, and then [do something that can be done in $k$ ways].

Well, once you've chosen $k$ objects from $n$, what is there that one could do next, that involves a choice among $k$ alternatives?

Once you've got that, you've got a procedure that can be performed in $k\binom nk$ ways. Then try to think of another procedure which would have the same effect, but which would naturally be counted as $n\binom{n-1}{k-1}$.