Combinatorial proof for: $\left(\!{n \choose r}\!\right) = \left(\!{n \choose {r-1}}\!\right) + \left(\!{ {n - 1} \choose r }\!\right) $

Question

Without algebraically manipulating this following equality (i.e. reducing down to $n - 1 +r\choose n-1 $ etc. ), what is a combinatorial proof for this following equation?:

$$ \left(\!\!{n \choose r}\!\!\right) = \left(\!\!{n \choose {r-1}}\!\!\right) + \left(\!\!{ {n - 1} \choose r }\!\!\right) $$

I can easily understand the LHS: we're placing r indistinguishable items into n distinguishable bins. Hence, n multichoose r.

However, as for the RHS, I'm having trouble understanding the disjoint cases here that allows for the use of The Sum Rule.

Answer 1

Consider the two cases, which are based on what you can do with bin $n$:

• either you decide to use bin $n$, so at least one item gets placed in it, after which you have to place $r - 1$ items to $n$ bins, or
• bin $n$ is not used at all, which means you have to place $r$ indistinguishable items to $n - 1$ bins

Therefore,

$$ \def\multiset#1#2{{\left(\kern-.3em\left(\genfrac{}{}{0pt}{}{#1}{#2}\right)\kern-.3em\right)}} \multiset{n}{r} = \multiset{n}{r - 1} + \multiset{n - 1}{r} $$

Answer 2

Left hand side: total number of multisets with size r on an n-element set.

Right hand side: Pick a certain element $x$ of the $n$-element set. Break the set of all multisets into 2 types: those containing an instance of $x$ and those not containing an instance of $x$.

Answer 3

We have that

$$\left(\!\!{n \choose r}\!\!\right)=\binom{n+r-1}r$$

Thus your identity is equivalent to this other

$$\binom{n+r-1}r=\binom{n+r-2}{r-1}+\binom{n+r-2}{r}$$

Then naming $m:=n+r-1$ your identity is equivalent to prove that

$$\binom{m}r=\binom{m-1}{r-1}+\binom{m-1}r$$

what can be proved easily from the definition of binomial coefficient, that is

$$\binom{m-1}{r-1}+\binom{m-1}r=\frac{(m-1)!}{(r-1)!(m-r)!}+\frac{(m-1)!}{r!(m-r-1)!}\\=\frac{(m-1)!(r+m-r)}{r!(m-r)!}=\frac{m!}{r!(m-r)!}=\binom{m}r$$