Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question

3 Answers 3

up vote 3 down vote accepted

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

share|improve this answer
    
This addresses the question directly. (+1) –  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$.

share|improve this answer
    
Both answers are really good, and I upvoted both, however, I can only choose one as an answer... –  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}$

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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