17. Consider the matching problem, Example 5m, and define A_N to be the number of ways in which the N men can select their hats so that no man selects his own. Argue that A_N = (N - 1)(A_N-1 + A_N-2)

This formula, along with the boundary conditions A₁ = 0, A₂ = 1, can then be solved for A_N, and the desired probability of no matches would be A_N/N!.

HINT: After the first man selects a hat that is not his own, there remain N - 1 men to select among a set of N - 1 hats that does not contain the hat of one of these men. Thus there is one extra man and one extra hat. Argue that we can get no matches either with the extra man selecting the extra hat or with the extra man not selecting the extra hat.