Proof Perms (1 Viewer)

moderntortoisecat · Jan 31, 2024

Prove that nPr = (n-2)Pr + 2r. (n-2)P(r-1) + r(r-1) x (n-2)P(r-2)

liamkk112 · Jan 31, 2024

by definition $^nP_r = \frac{n!}{(n-r)!}$

working from the RHS to arrive at the LHS:
RHS = $\frac{(n-2)!}{(n-r-2)!} + \frac{2r(n-2)!}{(n-r-1)!} + \frac{r(r-1)(n-2)!}{(n - r)!}$ by definition of permutation
= $\frac{(n-r-1)(n-r)(n-2)!}{(n-r)(n-r-1)(n-r-2)!} + \frac{2r(n-r)(n-2)!}{(n-r)(n-r-1)!} + \frac{r(r-1)(n-r)!}{(n-r)!}$ to make a common denominator
= $\frac{(n-r-1)(n-r)(n-2)!}{(n-r)!} + \frac{2r(n-r)(n-2)!}{(n-r)!} + \frac{r(r-1)(n-r)!}{(n-r)!}$ by definition of factorial
= $\frac{(n-2)!(n^2 -nr -nr +r^2 - n + r +2rn - 2r^2 +r^2 - r)}{(n-r)!}$ by expanding brackets
= $\frac{(n-2)! (n^2 -n)}{(n-r)!}$ by simplifying
= $\frac{(n-2)! n(n-1)}{(n-r)!}$ by factorising
= $\frac{n!}{(n-r)!}$ by definition of factorial
= $^nP_r$ = LHS as required

moderntortoisecat · Jan 31, 2024

Just a question, when making a common denominator, do u not multiply by the factorial, for example for the first fraction, would u not multiply it by (n-r-1)! ?

kendricklamarlover101 · Jan 31, 2024

moderntortoisecat said:
Just a question, when making a common denominator, do u not multiply by the factorial, for example for the first fraction, would u not multiply it by (n-r-1)! ?

the both have a common factor of (n-r-2)! so u can just multiply it by (n-r-1) like how 1/3 + 1/6 = 2/6 + 1/6 instead of 6/18 + 3/18

liamkk112 · Jan 31, 2024

moderntortoisecat said:
Just a question, when making a common denominator, do u not multiply by the factorial, for example for the first fraction, would u not multiply it by (n-r-1)! ?

(n-r)! = (n-r) (n-r-1) (n-r-2)! by definition of factorial, so it’s not necessary to multiply by the whole factorial here, u could technically do so as it would still make a common denominator but it will make the algebra unnecessarily difficult

Luukas.2 · Jan 31, 2024

As a general rule, unravelling the larger factorials makes for easier algebra:

$\begin{align*} \text{Required to Prove:} \qquad ^nP_r &=\ ^{n-2}P_r + 2r ^{n-2}P_{r-1} + r(r-1) ^{n-2}P_{r-2} \\ \\ \text{RHS} &= \frac{(n-2)!}{(n-r-2)!} + \frac{2r(n-2)!}{(n-r-1)!} + \frac{r(r-1)(n-2)!}{(n - r)!} \qquad \text{as, by definition, $^nP_r = \frac{n!}{(n - r)!}$} \\ &= \frac{(n-2)!}{(n-r-2)!} + \frac{2r(n-2)!}{(n-r-1)(n-r-2)!} + \frac{r(r-1)(n-2)!}{(n - r)(n-r-1)(n-r-2)!} \\ &= \frac{(n-2)!}{(n-r-2)!}\left[1 + \frac{2r}{n-r-1} + \frac{r(r-1)}{(n - r)(n-r-1)}\right] \\ &= \frac{(n-2)!}{(n-r-2)!} \times \frac{(n-r)(n-r-1) + 2r(n - r) + r(r-1)}{(n - r)(n-r-1)} \\ &= \frac{(n-2)!\left[\left(n^2 - 2nr + r^2 - n + r\right) + \left(2nr - 2r^2\right) + \left(r^2 - r\right)\right]}{(n-r)!} \\ &= \frac{(n-2)!\left(n^2 - n\right)}{(n-r)!} \\ &= \frac{(n-2)! \times n(n - 1)}{(n-r)!} \\ &= \frac{n!}{(n-r)!} \\ &= ^nP_r \\ &= \text{LHS} \end{align*}$

Or...

$\begin{align*} \text{LHS $-$ RHS} &= \frac{n!}{(n-r)!} - \frac{(n-2)!}{(n-r-2)!} - \frac{2r(n-2)!}{(n-r-1)!} - \frac{r(r-1)(n-2)!}{(n - r)!} \qquad \text{as, by definition, $^nP_r = \frac{n!}{(n - r)!}$} \\ &= \frac{n(n - 1) \times (n-2)!}{(n - r)(n -r-1) \times (n - r - 2)!} - \frac{(n-2)!}{(n-r-2)!} - \frac{2r(n-2)!}{(n-r-1)(n-r-2)!} - \frac{r(r-1)(n-2)!}{(n - r)(n-r-1)(n-r-2)!} \\ &= \frac{(n-2)!}{(n-r-2)!}\left[\frac{n(n - 1)}{(n-r)(n-r-1)} - 1 - \frac{2r}{n-r-1} - \frac{r(r-1)}{(n - r)(n-r-1)}\right] \\ &= \frac{(n-2)!}{(n-r-2)!} \times \frac{n(n - 1) - (n-r)(n-r-1) - 2r(n - r) - r(r-1)}{(n - r)(n-r-1)} \\ &= \frac{(n-2)!}{(n-r)!}\left[\left(n^2 - n\right) - \left(n^2 - 2nr + r^2 - n + r\right) - \left(2nr - 2r^2\right) - \left(r^2 - r\right)\right] \\ &= \frac{(n-2)!}{(n-r)!} \times 0 \\ &= 0 \\ \text{Thus,} \qquad \text{LHS} &= \text{RHS} \end{align*}$

Proof Perms (1 Viewer)

moderntortoisecat

New Member

liamkk112

Well-Known Member

moderntortoisecat

New Member

kendricklamarlover101

Member

liamkk112

Well-Known Member

Luukas.2

Well-Known Member

Users Who Are Viewing This Thread (Users: 0, Guests: 1)