A permutation $\pi \in S_n$ is an involution, when $\pi^2 = \text{id}$.
How can one show for the amount $I_n$ of the involutions in $S_n$ the following recursion:
$$I_{n+1} = I_n + nI_{n-1}$$
whereby $I_0 = 1$?
In another post I have read that an involution is any permutation $\pi$ such that $\pi^2 = \text{id}$. Hence, the number of involutions of $S_n$ will be the number of permutations $\pi \in S_n$ such that $\sigma$ has order $2$.
But that still doesn't help me in finding out how to show the recursion..
Hint: An involution of $\{1, \dots, n+1\}$ either sends $n+1$ to $n+1$ or to some other number.