Originally Posted by

**Kakariki** Hey,

I am working through some review questions for my mid term, and came across this problem:

Prove:

$\displaystyle 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):

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

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

$\displaystyle = \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.*

$\displaystyle = \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 $\displaystyle \frac{r}{r}=1$ , and the second one by $\displaystyle \frac{n-r}{n-r}=1$...this is a

pretty standard trick in many parts of mathematics.

$\displaystyle = \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 $\displaystyle n>1\,,\,\,n(n-1)!=(n-1)!n=n!$ , so $\displaystyle (r-1)!r=r!$ on the left fraction's denominator , and $\displaystyle (n-r)(n-r-1)!=(n-r)!$ , on the right one's denominator.

$\displaystyle = \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 $\displaystyle (n-1)!$ in the numerator!

$\displaystyle = \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*

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

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

Read the second note in blue

$\displaystyle = \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.

- Thanks in advanced!