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

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.

• Your formula is false: the first term in the r.h.s. should be $\dbinom{n-1}{r-1}$. – Bernard Feb 12 '18 at 19:27

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}$$

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$.

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$$