Looking for an intuitive explanation for a basic combinatorial identity I'm looking for an intuitive explanation for this identity:
$${n \choose k} = \frac{n}{k}{n-1 \choose k-1}$$
for $0 < k \leq n$.
The math adds up, but I can't see why it's true. I'd expect that choosing $k$ elements from an $n$-set would be like choosing $k-1$ elements from an $(n-1)$-set, then add an $n$th element to the set, and choose another element from the $n - k + 1$ not-yet-chosen elements. But I guess I'm missing something.
Can anyone provide some intuition?
 A: It's probably easiest to see as follows.  Choose the "first" element; there are $n$ ways to do this.  Now choose $k-1$ elements from the remaining $n-1$; there are ${n-1\choose k-1}$ ways to do this.  That gives you $n{n-1\choose k-1}$, but you've overcounted: for example, $\lbrace 1,2,3\rbrace$ is counted separately from $\lbrace 2,1,3\rbrace$, since your first choice was $1$ in the former case and $2$ in the latter.  So you divide out by the number of distinct ways of selecting a "first" element out of the $k$ that you've chosen; that gives you the additional factor of $1/k$.
A: One can write it like this:
$$k{n \choose k} = n{n-1 \choose k-1}.$$
First you choose $k$ out of $n$; then you choose one of the $k$ to be the leader.  There are $\binom nk$ ways to make the first choice, and then $k$ ways to make the second choice.  That's the left side of the identity.
Alternatively, first you choose one of the $n$ to be the leader; then you choose $k-1$ of the remaining $n-1$ to be the others in the group of $k$.  That's the right side of the identity.
A: It is equivalent to $${n\choose r}{r\choose 1}={n\choose 1}{n-1\choose r-1}$$
