Simplification of fraction with factorials

Question

I'm stuck on a simplification, used to prove $C(n - 1, r - 1) + C(n - 1, r) = C(n, r)$

Could somebody clarify the step(s) from: $\frac{(n - 1)!}{(r - 1)!(n - r)!} + \frac{(n - 1)!}{r!(n - r - 1)!}$ to $\frac{r(n - 1)!}{r!(n - r)!} + \frac{(n - r)(n - 1)!}{r!(n - r)!}$ (or $\frac{r(n - 1)! +(n - r)(n - 1)!}{r!(n - r)!}$).

I'm stuck making the denominators common via multiplication: I can't seem to work away the factorial expressions. $\frac{(n-1)!r!(n-r-1)!}{(r-1)!(n-r)!r!(r-n-1)!} + \frac{(n-1)!(r-1)!(n-r)!}{r!(n-r-1)!(r-1)!(n-r)!}$.

Any help would be very welcome!

Answer 1

Since $$ r!=r(r-1)! $$ and $$ (n-r)!=(n-r)(n-r-1)!, $$ we have the equivalent algebraic identities: $$\begin{eqnarray*} (r-1)! &=&\frac{r!}{r} \\ (n-r-1)! &=&\frac{(n-r)!}{n-r}. \end{eqnarray*}$$ So \begin{eqnarray*} \frac{(n-1)!}{(r-1)!(n-r)!}+\frac{(n-1)!}{r!(n-r-1)!} &=&\frac{(n-1)!}{\frac{ r!}{r}(n-r)!}+\frac{(n-1)!}{r!\frac{(n-r)!}{n-r}} \\ &=&\frac{r(n-1)!}{r!(n-r)!}+\frac{(n-r)(n-1)!}{r!(n-r)!} \\ &=&\frac{r(n-1)!+(n-r)(n-1)!}{r!(n-r)!}\\ &=&\frac{(r+n-r)(n-1)!}{r!(n-r)!} \\ &=&\frac{n(n-1)!}{r!(n-r)!} \\ &=&\frac{n!}{r!(n-r)!}. \end{eqnarray*}

Answer 2

You can think it combinatorially in this way(Avoiding those calculations),

Take a group of n people, Point out a fixed person say A, Now say you have to select r persons from those n people.You can do this by breaking it up into two cases as follows.

In one case you can select A and select $r-1$ persons from the rest $n-1$ persons in $\binom{n-1}{r-1}$ ways.

In the other case you wont select A at all, so you must select $r$ persons from the rest $n-1$ persons in $\binom{n-1}{r}$ ways

As both the cases are disjoint so they must add up to choosing r persons from n persons.

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

Answer 3

Look at the term $\dfrac{(n-1)!}{(r-1)!(n-r)!}$

Multiply top and bottom by $r$. The new top is $r(n-1)!$.

The new bottom is $r(r-1)!(n-r)!$. But $r(r-1)!=r!$, so the new bottom is $r!(n-r)!$.

For the simplification of the expression $\dfrac{(n-1)!}{r!(n-r-1)!}$, do the same sort of thing, but multiply top and bottom by $n-r$.

Once you have performed these two simplifications, the two expressions have the same denominator $r!(n-r)!$, so you can safely add the numerators.

Remark: It can also be done the way you attempted, but the expressions become much more complicated-looking. To use an analogy, suppose that we want to find the sum $\frac{5}{48}+\frac{11}{72}$. We could bring the expressions to the common denominator $48\cdot 72$. But it is easier to multiply top and bottom of the first term by $3$, and to multiply top and bottom of the second by $2$, getting the "small" common denominator $144$.