# Prove by Combinatorial Argument that $\binom{n}{k}= \frac{n}{k} \binom{n-1}{k-1}$

This is a question from my first proofs homework and I am confused about the combinatorial argument aspect. I already did the algebraic proof. I think I am supposed to put into words what both sides represent? So the LHS would be the number of ways of picking a committee of $k$ members from $n$ people, or number of subsets of size $k$ from a total of $n$, but I don't know how to articulate what is happening on the RHS.

Here's a hint. Try multiplying through by $k$, so it's at least obvious that both sides are integers. Then what you want to show is that $k\binom{n}{k} = n\binom{n-1}{k-1}$. The LHS is now the number of ways to select a committee of $k$ members from $n$ people along with a decision of which of those $k$ will be chairperson. Can you reinterpret this to get the RHS?.
Your expression can be rewritten as $$\binom{n}{k} \binom{k}{1}=\binom{n}{1}\binom{n-1}{k-1}$$ Hence LHS can be interpreted as the number of ways to select $k$ unique items out of $n$ AND then one out of these $k$. Then RHS is the number of ways to select one item out of $n$ AND then $k-1$ out of the remaining $n-1$.
• It seems worth pointing out that this argument works more generally, in the sense that you can replace all the $1$'s by $m$ for any $m\leq k$. – Andreas Blass Mar 5 '13 at 17:39