Write out the terms on the RHS using the permutation definition.

Question

ScanSolve AI Tutor · Accepted Answer

To prove the identity ^nP_r = ^n−1P_r + r · ^n−1Pr−1, we will start with the right-hand side (RHS) and transform it into the left-hand side (LHS) using the definition of permutations, ^kP_m = (k!)/((k−m)!). Step 1: Write out the terms on the RHS using the permutation definition. ^n−1P_r = ((n−1)!)/(((n−1)−r)!) = ((n−1)!)/((n−r−1)!); ^n−1Pr−1 = ((n−1)!)/(((n−1)−(r−1))!) = ((n−1)!)/((n−1−r+1)!) = ((n−1)!)/((n−r)!) Step 2: Substitute these expressions back into the RHS. RHS = ((n−1)!)/((n−r−1)!) + r · ((n−1)!)/((n−r)!) Step 3: Find a common denominator for the two terms. We know that (n−r)! = (n−r) · (n−r−1)!. Multiply the first term by (n−r)/(n−r) to get a common denominator of (n−r)!. RHS = ((n−1)!)/((n−r−1)!) · ((n−r))/((n−r)) + (r(n−1)!)/((n−r)!); RHS = ((n−r)(n−1)!)/((n−r)!) + (r(n−1)!)/((n−r)!) Step 4: Combine the terms over the common denominator. RHS = ((n−r)(n−1)! + r(n−1)!)/((n−r)!) Step 5: Factor out (n−1)! from the numerator. RHS = ((n−1)! · ((n−r) + r))/((n−r)!); RHS = ((n−1)! · (n−r+r))/((n−r)!); RHS = ((n−1)! · n)/((n−r)!) Step 6: Rearrange the numerator to form n!. Since n! = n · (n−1)!, we can rewrite the numerator. RHS = (n!)/((n−r)!) Step 7: Recognize this as the definition of ^nP_r. RHS = ^nP_r This matches the LHS. Therefore, the identity is proven: ^nP_r = ^n−1P_r + r · ^n−1Pr−1

Write out the terms on the RHS using the permutation definition.

Answer

Step-by-step solution