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.