17
$\begingroup$

Suppose we want to prove $$ k \binom{n}{k} = n \binom{n-1}{k-1}$$

In the LHS we are choosing a team of $k$ players from $n$ players. Then we are choosing a captain. In the RHS we are choosing a captain from the $n$ players. Then we are choosing the remaining $k-1$ players from the $n-1$ players.

Is this a correct interpretation?

  • 2
    I don't see anything faulty.2011-12-28
  • 7
    Yes, that interpretation is correct (and well-put). Algebraically, it's just $k{n\choose k} = kn!/(k!(n-k)!) = n!/((k-1)!(n-k)!) = n(n-1)!/((k-1)!(n-k)!)=n{{n-1}\choose{k-1}}$.2011-12-28
  • 0
    if the captain is a player, then the LHS is OK, but the RHS is not because you are using $n-1$ in $ n \binom{n-1}{k-1}$2011-12-28
  • 0
    I think this proof is correct. @EmmadKareem - It's $n-1$ because the choice of captain has already been made.2011-12-28
  • 1
    @James : I think you've answered your own question.2011-12-28
  • 0
    Got it, thanks.2011-12-28

4 Answers 4