Question

4. Here is a fact about permutations: (**) nPk = n!/(n-k)!, for all k € ≤ n. Let’s prove this via mathematical induction for the fixed case k=3.

(i) Write clearly the statement (**) we wish to prove. Be sure your statement includes the phrase “for all n” .

(ii) State explicitly the assumption in (**) we will thus automatically make about k=2.

(iii) Now recall that to prove by induction means to show that If mPk = m!/(m-k)! is true for all € k ≤ m then m+1Pk = (m+1)!/((m+1)-k )! for all € k ≤ m +1 must also be true. State what we must prove in the case k=3. Include the relevant statement about k=2 here, as you will need to use it in (iv).

(iv) OK so now prove (**) for the case k=3.

(a) Verify the theorem is true for the “base case” n=3 (I.E) that (**) is true for k=0,1,2,3 when n=3. You can do these four verifications by elementary means. Just remember what we mean by permutations, and thus convince us these four statements are true.

(b) Now use your cleverness to prove the underlined statement (iii) is true.

(c) Now state the fact that you have proven (**) to be true for k=3 and all n.

Answer 1