I'm stuck on the proof in the title.

Consider a derangement on {1,2,...,n}

Let

X_{k}: set of derangements with the last element k

Y_{k}: set of derangements in X_{k}with the k-th element n

Z_{k}: set of derangements in Xk with the k-th element not n

Then, (i) if entries n and k are deleted in the derangements in Y_{k}, the result is a derangement on {1,2,...,k-1,k+1,...,n} and (ii)Z_{k}is the set of derangements on {1,2,...,n,...,n-1}

I tried to justify (i) by starting with the supposition that x_{i}= i in the new derangement.

If , then since such x_{i}s are unaffected by the deletion, x_{i}= i in the original derangement, so this is a contradiction.

But I don't know how to make a contradiction for .

I don't see what's wrong with having x_{k+2}=k+1 in the original derangement (and then having x_{k+1}=k+1 in the new arrangement, and not result in a derangement.)

For (ii), I need help getting started with the proof.