SOLUTION: Show that C(n,r)= C(n-1,r-1)+C(n-1,r) NOTE: Professor said that you can start in either left side or right side

Algebra ->  Permutations -> SOLUTION: Show that C(n,r)= C(n-1,r-1)+C(n-1,r) NOTE: Professor said that you can start in either left side or right side      Log On


   

Question 970351: Show that C(n,r)= C(n-1,r-1)+C(n-1,r)

NOTE: Professor said that you can start in either left side or right side
Answer by jim_thompson5910(35256) About Me  (Show Source):
You can put this solution on YOUR website!
C%28n%2Cr%29+=+%28n%21%29%2F%28r%21%2A%28n-r%29%21%29 by definition


-------------------------------------------------------


C%28n%2Cr%29+=+%28n%21%29%2F%28r%21%2A%28n-r%29%21%29


Replace every 'n' with 'n-1'. Replace every 'r' with 'r-1'


C%28n-1%2Cr-1%29+=+%28%28n-1%29%21%29%2F%28%28r-1%29%21%2A%28+n+-+1+-+r+%2B+1+%29%21%29


C%28n-1%2Cr-1%29+=+%28%28n-1%29%21%29%2F%28%28r-1%29%21%2A%28n+-+r%29%21%29 I'm going to call this equation Q


-------------------------------------------------------


C%28n%2Cr%29+=+%28n%21%29%2F%28r%21%2A%28n-r%29%21%29


C%28n-1%2Cr%29+=+%28%28n-1%29%21%29%2F%28r%21%2A%28+n+-+1+-+r+%29%21%29 Replace every 'n' with 'n-1'. I'm going to call this equation R


-------------------------------------------------------


we will use these ideas


n%21+=+n%2A%28n-1%29%21


r%21+=+r%2A%28r-1%29%21


%28n-r%29%21+=+%28n-r%29%2A%28n+-+r-1%29%21


to help us do the proof.


-------------------------------------------------------


Now onto the main proof. I'm only going to manipulate the right side of the equation to transform it into the left side.


C%28n%2Cr%29+=+C%28n-1%2Cr-1%29%2BC%28n-1%2Cr%29


Substitute equation Q and equation R (see above)


Use the tricks shown above (eg: to write r%21 as r%2A%28r-1%29%21).





I'm highlighting the common terms (shared between the fractions) in red


Factor out the common terms














C%28n%2Cr%29+=+%28+n%21+%29%2F%28+r%21+%2A+%28n-r%29%21+%29


C%28n%2Cr%29+=+C%28n%2Cr%29 So the identity is confirmed.