# Combination Proof - Need help understanding steps in answer

• February 4th 2010, 06:20 PM
Kakariki
Combination Proof - Need help understanding steps in answer
Hey,

I am working through some review questions for my mid term, and came across this problem:
Prove:
$C(n , r) = C(n-1 , r -1) + C(n-1 , r )$

I tried the problem, and my semi-complete solution looks just like the answer in the back, but I only got so far. Here is the answer in the back (with notes of me asking what is going on, and why):

$LS = \frac {n!}{(n-3)!r!}$

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

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

*Above is how far I got, after this I have little understanding what is happening.*

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

*Okay, so where did the r come from on top on the left fraction? as-well as the r on the bottom. The right fraction suddenly is multiplied by "(n-r)"...why?*

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

*this step also doesn't make sense to me. How does the bottom of the left fraction become that? I realize they have a common denominator now, but I do not understand their multiplication. On either side.*

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

*Do not understand the addition here, at all. A webpage explaining something similar may clear this up. Will be searching after I finish typing this post*

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

*this makes sense, they added the r and -r together to get 0, so just left with the n on top*

$= \frac {!n}{(n-r)!r!}$

*do not understand how the "(n-1)" disappears from the top here.*

$= \frac {!n}{(n-r)!r!}$

*This is how it is shown in the book. I assume the factorial still applies even when it is infront of the n. I understand this to be what C(n,r) looks like.

Hopefully the point of this thread makes sense to you. I am asking questions about an answer in the back, that I do not understand, and am looking for help with.

• February 4th 2010, 07:09 PM
tonio
Quote:

Originally Posted by Kakariki
Hey,

I am working through some review questions for my mid term, and came across this problem:
Prove:
$C(n , r) = C(n-1 , r -1) + C(n-1 , r )$

I tried the problem, and my semi-complete solution looks just like the answer in the back, but I only got so far. Here is the answer in the back (with notes of me asking what is going on, and why):

$LS = \frac {n!}{(n-3)!r!}$

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

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

*Above is how far I got, after this I have little understanding what is happening.*

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

*Okay, so where did the r come from on top on the left fraction? as-well as the r on the bottom. The right fraction suddenly is multiplied by "(n-r)"...why?*

Both fractions are multiplied by 1, which doesn't change them: the first one is multiplied by $\frac{r}{r}=1$ , and the second one by $\frac{n-r}{n-r}=1$...this is a

pretty standard trick in many parts of mathematics.

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

*this step also doesn't make sense to me. How does the bottom of the left fraction become that? I realize they have a common denominator now, but I do not understand their multiplication. On either side.*

For any natural $n>1\,,\,\,n(n-1)!=(n-1)!n=n!$ , so $(r-1)!r=r!$ on the left fraction's denominator , and $(n-r)(n-r-1)!=(n-r)!$ , on the right one's denominator.

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

*Do not understand the addition here, at all. A webpage explaining something similar may clear this up. Will be searching after I finish typing this post*

They just added the fractions and factored out $(n-1)!$ in the numerator!

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

*this makes sense, they added the r and -r together to get 0, so just left with the n on top*

$= \frac {!n}{(n-r)!r!}$

*do not understand how the "(n-1)" disappears from the top here.*

Read the second note in blue

$= \frac {!n}{(n-r)!r!}$

*This is how it is shown in the book. I assume the factorial still applies even when it is infront of the n. I understand this to be what C(n,r) looks like.

The ! sign in front of a number is either a typographic error, or else some non-standard notation they explain somewhere in the book, or somebody was high when printing the book, but it definitely is not the same as the ! sign AFTER the number, which is the standard, correct way to write it.

Tonio

Hopefully the point of this thread makes sense to you. I am asking questions about an answer in the back, that I do not understand, and am looking for help with.