SOLUTION: Prove (n+1)p(r) = (n)p(r) + 4.(n)p(r-1)

Click here to see ALL problems on Permutations

Question 1110201: Prove (n+1)p(r) = (n)p(r) + 4.(n)p(r-1)

Found 2 solutions by greenestamps, ikleyn:
Answer by greenestamps(13200)   (Show Source):
You can put this solution on YOUR website!

Interesting problem....

But you didn't state the equation correctly. The equation you show has many counterexamples.

For n=6 and r=3, the formula says

7P3 = 6P3+4*6P2. But

7P3 = 7*6*5 = 210
6P3 = 6*5*4 = 120
6P2 = 6*5 = 30

and

210 = 120 + 4*30

is not true.

The interesting problem is when the formula is stated correctly:

(n+1)Pr = nPr + r*nP(r-1)

This is easy to prove algebraically, although the nomenclature is ugly....

(n+1)Pr = (n+1)(n)(n-1)(n-2)...(n-(r-2)) = (n+1)(n)(n-1)(n-2)...(n-r+2)

nPr = (n)(n-1)(n-2)...(n-(r-2))(n-(r-1)) = (n)(n-1)(n-2)...(n-r+2)(n-r+1)

nP(r-1) = (n)(n-1)(n-2)...(n-(r-2)) = (n)(n-1)(n-2)...(n-r+2)

Then

nPr + r*nP(r-1) =

[(n)(n-1)(n-2)...(n-r+2)](n-r+1) + r[(n)(n-1)(n-2)...(n-r+2)] =

[(n)(n-1)(n-2)...(n-r+2)][(n-r+1)+r] =

[(n)(n-1)(n-2)...(n-r+2)](n+1)=

(n+1)(n)(n-1)(n-2)...(n-r+2)

(n+1)Pr

Answer by ikleyn(52784)   (Show Source):
You can put this solution on YOUR website!
.
Prove (n+1)p(r) = (n)p(r) + 4.(n)p(r-1)
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Wrong identity.

To see the correct version (with the Proof), look into the lesson
    - Binomial Theorem, Binomial Formula, Binomial Coefficients and Binomial Expansion, Problem 1
in this site.