In helping someone with a coding challenge for calculating the derangement number, I learned that the formula I came up with:
$$d(n)=n\cdot d(n-1)+(-1)^n$$
is not the one that most references quote: both Wikipedia and Wolfram list:
$$d(n)=(n-1)[(d(n-1)+d(n-2)]$$
instead. I can see how the second formulation is easier to arrive at intuitively, but I can't think how these two can be proven to be the same. Wolfram lists both, and indeed the series of $d(n)$ are identical empirically, but how would one go about proving they are the same?
The first formula can easily be used to derive the second formula ... \begin{eqnarray*} d_{n-1}&=&(n-1)d_{n-2}+(-1)^{n-1} \\ d_{n}&=&nd_{n-1}+(-1)^{n} \\ &=&(n-1)d_{n-1}+d_{n-1}+(-1)^{n} \\ &=&(n-1)d_{n-1}+(n-1)d_{n-2}+\underbrace{(-1)^{n-1}+(-1)^{n}}_{=0}. \\ \end{eqnarray*}