SOLUTION: How can i show that nPr = (n-1)P(r) + r*[(n-1)P(r-1)

Algebra ->  Permutations -> SOLUTION: How can i show that nPr = (n-1)P(r) + r*[(n-1)P(r-1)      Log On


   



Question 934927: How can i show that nPr = (n-1)P(r) + r*[(n-1)P(r-1)
Answer by Edwin McCravy(20054) About Me  (Show Source):
You can put this solution on YOUR website!
The permutation formula is 

xPy = x%21%2F%28x-y%29%21

So we are to prove:

nPr ≟ (n-1)P(r) + r*((n-1)P(r-1)), which becomes:

n%21%2F%28n-r%29%21%28%28n-1%29%21%2F%28n-1-r%29%21%29%2Br%2A%28%28n-1%29%21%2F%28%28n-1%29-%28r-1%29%29%21+%29

n%21%2F%28n-r%29%21%28%28n-1%29%21%2F%28n-1-r%29%21%29%2Br%2A%28%28n-1%29%21%2F%28n-1-r%2B1%29%21+%29

n%21%2F%28n-r%29%21%28%28n-1%29%21%2F%28n-1-r%29%21%29%2Br%2A%28%28n-1%29%21%2F%28n-r%29%21%29

--------------------------------------------------------------------
Proof:

nPr = n%21%2F%28n-r%29%21%22%22=%22%22n%2A%28n-1%29%21%2F%28%28n-r%29%28n-r-1%29%21%29%22%22=%22%22%28n%2F%28n-r%29%29%2A%28%28n-1%29%21%2F%28n-1-r%29%21%29%22%22=%22%22

Now divide n%2F%28n-r%29 by long division:

                 1                  
           n-r)n+0            
               n-r
                 r

           The quotient is 1%2Br%2F%28n-r%29

%281%2Br%2F%28n-r%29%29%2A%28%28n-1%29%21%2F%28n-1-r%29%21%29%22%22=%22%22%22%22=%22%22
%28%28n-1%29%21%2F%28n-1-r%29%21%29%2B%28+r%28n-1%29%21%2F%28n-r%29%28n-1-r%29%21+%29%22%22=%22%22%28%28n-1%29%21%2F%28n-1-r%29%21%29%2Br%2A%28%28n-1%29%21%2F%28n-r%29%28n-r-1%29%21+%29%22%22=%22%22
%28%28n-1%29%21%2F%28n-1-r%29%21%29%2Br%2A%28%28n-1%29%21%2F%28n-r%29%21+%29%22%22=%22%22


nPr = (n-1)P(r) + r
 
Edwin