2

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?

εν οίδα ότι ουδέν οίδα
  • 1,138
  • 1
    The standard procedure is to find a counting problem and solve it in two different ways: one that gives you the result on the left, and one that gives you the result on the right. If you end up doing lots of symbol manipulation, it's not really a combinatorial proof. – genisage Oct 21 '14 at 23:14
  • So you're telling me this can't be solved using a combinatorial proof? – εν οίδα ότι ουδέν οίδα Oct 21 '14 at 23:17
  • Not at all. It can be done in a bunch of different ways, but if you want a combinatorial proof, you're not going to try to transform one side of the equation into the other using algebra. – genisage Oct 21 '14 at 23:18
  • Ah okay, sorry I am a bit confused on how to approach such a proof because the only example I did was Pascal's identity so I tried to somehow work similarly – εν οίδα ότι ουδέν οίδα Oct 21 '14 at 23:21

3 Answers3

8

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.

genisage
  • 427
4

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}$.

0

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.

Berci
  • 90,745