SOLUTION: Show that: n C r = [(n-2) C r] + 2[(n-2) C (r-1)] + [(n-2) C (r-2)]

Algebra ->  Permutations -> SOLUTION: Show that: n C r = [(n-2) C r] + 2[(n-2) C (r-1)] + [(n-2) C (r-2)]       Log On


   

Question 908843: Show that:
n C r = [(n-2) C r] + 2[(n-2) C (r-1)] + [(n-2) C (r-2)]

Answer by Edwin McCravy(20060) About Me  (Show Source):
You can put this solution on YOUR website!
%22nCr%22%22%3F=%3F%22%22%28n-r%29Cr%22%2B2%2A%22%28n-2%29C%28r-1%29%22%2B%22%28n-2%29C%28r-2%29%22

We will work with the right side:

%28n-2%29%21%2F%28r%21%28n-2-r%29%21%29%22%22%2B%22%222%2A%28n-2%29%21%2F%28r-1%29%21%28n%5E%22%22-2-%28r-1%29%29%21%22%22%2B%22%22%28n-2%29%21%2F%28r-2%29%21%28n%5E%22%22-2-%28r-2%29%29%21

%28n-2%29%21%2F%28r%21%28n-2-r%29%21%29%22%22%2B%22%222%2A%28n-2%29%21%2F%28r-1%29%21%28n%5E%22%22-2-%28r-1%29%29%21%22%22%2B%22%22%28n-2%29%21%2F%28r-2%29%21%28n%5E%22%22-2-%28r-2%29%29%21

%28n-2%29%21%2F%28r%21%28n-2-r%29%21%29%22%22%2B%22%222%2A%28n-2%29%21%2F%28r-1%29%21%28n-2-r%2B1%29%21%22%22%2B%22%22%28n-2%29%21%2F%28r-2%29%21%28n-2-r%2B2%29%21

Simplify and write letters before numbers:

%28n-2%29%21%2F%28r%21%28n-r-2%29%21%29%22%22%2B%22%222%2A%28n-2%29%21%2F%28%28r-1%29%21%28n-r-1%29%21%29%22%22%2B%22%22%28n-2%29%21%2F%28%28r-2%29%21%28n-r%29%21%29

Factor out (n-2)!



Write r! as r(r-1)(r-2)!
Write (r-1)! as (r-1)(r-2)!
Write (n-r)! as (n-r)(n-r-1)(n-r-2)!
Write (n-r-1)! as (n-r-1)(n-r-2)!



The LCD is r%28r-1%29%28r-2%29%21%28n-r%29%28n-r-1%29%28n-r-2%29%21



(1)  %28n-2%29%21%28%28+%28n-r%29%28n-r-1%29%2B2r%28n-r%29%2Br%28r-1%29%29%2F%28LCD%29%29+

Now we simplify the numerator of (1):

%28n-r%29%28n-r-1%29%2B2r%28n-r%29%2Br%28r-1%29

%28n-r%29%28n-r-1%29%2B2r%28n-r%29%2Br%28r-1%29

We factor (n-r) out of the first two terms:

%28n-r%29%28n-r-1%2B2r%29%2Br%28r-1%29

%28n-r%29%28n%2Br-1%29%2Br%28r-1%29

%28n-r%29%28%28n%2Br%29-1%5E%22%22%29%2Br%28r-1%29

Distribute the (n-r)

%28n-r%29%28n%2Br%29-%28n-r%29%2Br%28r-1%29

Multiply everything out to remove all the parentheses:

{{n^2-r^2-n+r+r^2-r}}}

The r's and rē's

n%5E2-n}

n%28n-1%29

Substitute for the numerator in (1)

(1)  %28n-2%29%21%28n%28n-1%29%29%2F%28LCD%29%29+

And when we multiply (n-2)! by that numerator,

(1)  %28n%28n-1%29%28n-2%29%21%29%2F%28LCD%29%29+

the numerator becones n!

(1)  n%21%2F%28LCD%29%29+

Next we simplify the LCD

LCD = r%28r-1%29%28r-2%29%21%28n-r%29%28n-r-1%29%28n-r-2%29%21

That is just r%21%28n-r%29%21

So now (1) becomes

(1)  n%21%2F%28r%21%28n-r%29%21%29

which is

(1)  nCr

Whew!

Edwin