SOLUTION: For positive integers n > r, show that: a) nCr = nC(n-r) b) nCr = (n-1)C(r-1) + (n-1)Cr

Algebra ->  Permutations -> SOLUTION: For positive integers n > r, show that: a) nCr = nC(n-r) b) nCr = (n-1)C(r-1) + (n-1)Cr      Log On


   

Question 1068818: For positive integers n > r, show that: a) nCr = nC(n-r) b) nCr = (n-1)C(r-1) + (n-1)Cr
Answer by swincher4391(1107) About Me  (Show Source):
You can put this solution on YOUR website!
a) We know that the formula for nCr = n%21%2F%28%28n-r%29%21%2Ar%21%29 = n%21%2F%28%28n-r%29%21%2A%28n-%28n-r%29%29%21%29 =
n%21%2F%28%28n-%28n-r%29%29%21%2A%28n-r%29%21%29 = highlight%28n%2AC%2A%28n-r%29%29
b) We know that the formula for nCr = n%21%2F%28%28n-r%29%21%2Ar%21%29= %28n+%2A+%28n-1%29%21%29%2F%28%28n-r%29%2A%28n-r-1%29%21%2Ar%2A%28r-1%29%21%29.
Usually proofs have some form of adding 0 or multiplying by 1 in a clever way. In this case we will represent n as n-r+r
%28%28n-r%2Br%29%2A+%28n-1%29%21%29%2F%28%28n-r%29%2A%28n-r-1%29%21%2Ar%2A%28r-1%29%21%29
Now distribute (n-1)!


Left hand fraction: cancel out n-r and combine r * (r-1)! to be r!
Right hand fraction: cancel out r and combine (n-r)*(n-r-1)! to be (n-r)!

Switch around n-r-1 to n-1-r, and we're basically done.

Rewrite n-r as (n-1)-(r-1) on the RHS fraction

highlight%28%28n-1%29%2AC%2Ar+%2B+%28n-1%29%2AC%2A%28r-1%29%29