Factorial Proof - ${n \choose r-1}+{n \choose r}={n+1 \choose r}$

Question

${n \choose r-1}+{n \choose r}={n+1 \choose r}.$

So what I tried to do was expand the first and second term.

$\frac{n!}{(r-1)!(n+1-r)!}+\frac{n!}{(r)!(n-r)!}.$

Then what I did was try to get common denominators.

$\frac{n!}{(r-1)!(n+1-r)(n-r)!}+\frac{n!}{(r)(r-1)!(n-r)!}.$

Then I attempted to combine and get the common denominator.

$\frac{(n!)(r)+(n!)(n+1-r)}{(r-1)!(n+1-r)(n-r)!(r)}.$

From here I simplified a bit more but didn't get a nice answer.

Some insight would be helpful.

Answer 1

\begin{eqnarray*}\binom{n}{r-1}+\binom{n}{r}&=&\frac{n!}{(n-(r-1))!(r-1)!}+\frac{n!}{(n-r)!r!}\\&=&\frac{n!r}{(n-r+1)!r!}+\frac{n!(n-r+1)}{(n-r+1)!r!}\\&=&\frac{n!r+n!n-n!r+n!}{(n-r+1)!r!}\\&=&\frac{n!n+n!}{(n+1-r)!r!}\\&=&\frac{(n+1)n!}{(n+1-r)!r!}\\&=&\frac{(n+1)!}{((n+1)-r)!r!}\\&=&\binom{n+1}{r} \end{eqnarray*}

Answer 2

Note that in the numerator we have $$ (n!)(r) + (n!)(n+1 - r) = (n!)(r + n-r+1) = (n!)(n+1) = (n+1)! $$ and in the denominator $$ (r-1)!\cdot r = r!\\ (n-r)!\cdot (n+1-r) = (n+1-r)! $$

Answer 3

Here is a combinatorial proof: Let $S$ be a set with $n+1$ elements, $\binom{n+1}{r}$ is the number of subsets with $r$ elements choosen from the set $S$. Now, take an elements $a \in S$. You can then devide the subsets with $r$ elements into the ones that contains $a$ and the ones that don't. The number of subsets with $r$ elements that contains $a$ is $\binom{n}{r-1}$ because you are choosing $r-1$ elements in $S-\{a\}$, which has size $n$. The number of subsets that without $a$ is $\binom{n}{r}$ because you are choosing $r$ elements in $S-\{a\}$ which has size $n$.

Answer 4

You start well: $$ \binom{n}{r-1}+\binom{n}{r}= \frac{n!}{(r-1)!\,(n-r+1)!}+\frac{n!}{r!\,(n-r)!} $$ Now it's best to collect all common terms. Not so different from what you did, but with less complications. Note you can collect

1. $n!$ in the numerator
2. $(r-1)!$ in the denominator, using $r!=r\,(r-1)!$
3. $(n-r)!$ in the denominator, using $(n-r+1)!=(n-r+1)\,(n-r)!$

Thus you can go on with $$ =\frac{n!}{(r-1)!\,(n-r)!}\left(\frac{1}{n-r+1}+\frac{1}{r}\right) $$ The part in parentheses can be rewritten as $\dfrac{n+1}{r(n-r+1)}$ so you have $$ =\frac{(n+1)\,n!}{r\,(r-1)!\,(n-r+1)\,(n-r)!}=\frac{(n+1)!}{r!\,(n+1-r)!}=\binom{n+1}{r} $$