The binomial coefficient - prove this property

Question

Prove that $$ {n\choose k}= \frac{n}{k} {n-1\choose k-1}$$ I have been thinking about it for a very long time and I have finally come to this solution:
First of all, multiply by $k$:
$${n\choose k}k = n {n-1 \choose k-1}$$
Let's say that we have a group of $n$ people. The left hand side first chooses $k$ of them who get a candy and then chooses $1$ from the chosen group to get a toy truck.
The right hand side first chooses one person who gets a candy and a toy truck and then chooses $n-1$ people to get a candy.

In both scenarios we have chosen exactly $k$ people, $k$ of them got a candy and $1$ of them got the toy truck. Thus, LHS and RHS are the same.

Is this solution valid to any extent?
What other ways to prove this are there? I tried induction - it works, too, but is a little tedious.

Answer 1

Another way is this:\begin{align}\binom nk&=\frac{n(n-1)\ldots(n-k+1)}{k(k-1)\ldots 1}\\&=\frac nk\times\frac{(n-1)(n-2)\ldots(n-k+1)}{(k-1)(k-2)\ldots1}\\&=\frac nk\times\binom{n-1}{k-1}.\end{align}

Answer 2

Yes, you are correct. The methodology of proof you have chosen is a combinatorical proof, showing that 2 scenarios in fact count the same things. See here for more info.

Answer 3

That is a lovely story proof and it sounds like you had fun coming up with it.

Well anyway, here is another which is perhaps a little more difficult to understand because it involves using the division principle. It is really no different mathematically, only in how you think about it:

Left Hand Side

You can pick $k$ people from $n$ for a $k$ person team in $\binom{n}{k}$ ways.

Right Hand Side

You can pick the 'first person' of the $k$ person team in $\binom{n}{1}=n$ ways, then the rest of the team in $\binom{n-1}{k-1}$ ways. Each team in these $n\binom{n-1}{k-1}$ is counted $k$ times (once for every possible 'first person'). We must therefore divide $n\binom{n-1}{k-1}$ by this multiplicity $k$ in order to count each team only once. Giving $\frac{n}{k}\binom{n-1}{k-1}$.