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!


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

  • $\begingroup$ This addresses the question directly. (+1) $\endgroup$ – robjohn Feb 12 '13 at 12:33

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

  • $\begingroup$ Both answers are really good, and I upvoted both, however, I can only choose one as an answer... $\endgroup$ – DiligoDiligentia Feb 12 '13 at 17:40

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.