How do you combinatorially prove the following? $$r \binom {n}{r} = n \binom {n-1}{r-1}$$
I find it easy to prove such equalities algebraically, but have a hard time finding the right combinatorial intuition.
Any advice for coming up with combinatorial proofs myself?
On
My go-to combinatorial argument falls along the line of "committee selection." (Albeit mostly because this idea was taught in my combinatorics class.) You have a collection of people, and want to pick them for a committee (and possible positions in that committee) in certain ways which are clearly equivalent, and yet lead to different calculations that lead to deducing the equality.
Sadly there's not much to "getting good" at them other than exposure. (Ironically I also find this method of proof much easier than the algebra, but I digress.)
For your case, let's argue as so...
We have $n$ people, and wish to have a committee of precisely $r$ people among them. How might we pick them? Moreover, we need to have a leader of the committee as well!
We could just pick the $r$ members of the group of $n$, and then the leader amongst the selected. There's $\binom n r$ possible ways to pick the committee, and $r$ possibilities for the leader among them. Thus, $r \binom n r$ possible committees.
Alternatively, let's say we set aside one particular person from our group of $n$ (maybe they only want to play along if they're the leader), and make a committee of $r-1$ members instead from the remaining $n-1$. There's $\binom{n-1}{r-1}$ ways to make the committee this way. However, the person set aside deserves a shot at being the leader anyways, and we still need one person to be the leader as well as give us our $r^{th}$ member, giving $n$ possible leaders. Thus, $n \binom{n-1}{r-1}$ possible committees.
Thus, we deduce
$$r \binom n r = n \binom{n-1}{r-1}$$
The first step is to interpret the expressions - what are they counting? There are some tricks to this. For instance, addition corresponds to a single choice out of two sets of options whereas multiplication corresponds to two choices from two sets of options. Another trick is to find dependencies - for instance in the expression $r\binom{n}{r}$, we see the $r$ twice, so we ought to investigate what it would mean if one of the $r$s represented a choice that was dependent on the other $r$. In particular, if $\binom{n}{r}$ counts $r$-subsets of $\{1,\cdots,n\}$ then $r$ by itself can be interpreted as how many ways there are to choose a single element of that $r$-subset.
We always phrase this in more familiar terms. For instance, instead of an $r$-subset of $\{1,\cdots,n\}$, we can think of a committee of $r$ people out of $n$ candidates. Then the special one of the $r$ members chosen for the other $r$ in the expression $r\binom{n}{r}$ can be interpreted as choosing a president. So $r\binom{n}{r}$ counts committees of $r$ people drawn from $n$ candidates with a single president.
A next step is to think about how to count this, but in a different way. If you think about the thing you're constructing in terms of "choices" that can be made while constructing it, you can change the order in which you make these choices. For instance, instead of choosing $r$ out of $n$ people for a committee and then choosing a president out of those $r$, which gives $r\binom{n}{r}$, you can instead pick the president ($n$ options) and then pick the $r-1$ non-president members of the committee out of the remaining $n-1$ people, which gives the equivalent expression $n\binom{n-1}{r-1}$.