The binomial coefficient - prove this property 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.
 A: 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}
A: 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}$. 
A: 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.
