Prove: Number of derangement is odd if and only if number of items is even . Let $D_n$ be a number of derangement of $n$ items. Prove that $D_n$ is odd if and only if $n$ is even. 
I was trying to use induction on the $!n=(n-1)(!(n-1)+!(n-2))$ recurrence relation but I can't derive the parity of the $!(n-2)$.
The other way I was thinking about is direct proof using the standard sum we get from  inclusion-exclusion principle $$n!\sum_{i=0}^{n}\frac{(-1)^i}{i!}$$ but I don't see how I can prove it's odd if and only if $n$ is even.
 A: It is possible to find the parity from the formula $$\sum_{i=0}^n (-1)^i \frac{n!}{i!}=\sum_{i=0}^n (-1)^i n(n-1)\cdots(i+1).$$
Working modulo $2$:


*

*If $n$ is even, then there is one non-zero contribution to the sum is when $i=n$, so we have an odd number.

*If $n$ is odd, then there are two non-zero contributions to the sum, when $i=n$ and when $i=n-1$, so we have an even number.
A: Generally, derangements come in pairs: the inverse of a derangement is a derangement. The exceptions are the fixed-point-free involutions, i.e., the permutations in which every cycle is a $2$-cycle. Thus the parity of the number of derangements is the same as the parity of the number of fixed-point-free involutions.
If $n$ is odd, there are no fixed-point-free involutions, so the number of derangements is even.
If $n$ is even, say $n=2k$, then the number of fixed-point-free involutions is
$(2k-1)(2k-3)(2k-5)\cdots3\cdot1$, an odd number.
Alternatively: Let $A_n$ be the number of even derangements of $n$ items, i.e., derangements which are even permutations; and let $B_n$ be the number of odd derangements. Establish the identity $A_n-B_n=(-1)^{n-1}(n-1)$. (Note that this is the value of a certain determinant, namely, the determinant of an $n\times n$ matrix with zeros on the main diagonal and ones everywhere else.) It follows that$$D_n=A_n+B_n=A_n-B_n+2B_n=(-1)^{n-1}(n-1)+2B_n\equiv n-1\pmod2.$$
Yet another way using the identity $D_n=nD_{n-1}+(-1)^n$ (which is easily derivable from the familiar inclusion-exclusion formula for $D_n)$. Clearly, if $n$ is even, then $D_n=nD_{n-1}+(-1)^n$ is odd. On the other hand, if $n$ is odd, then $nD_{n-1}$ is odd, and so $D_n=nD_{n-1}+(-1)^n$ is even.
A: Yet another way of showing the result is down your original path, using the recurrence relation $!n=(n-1)\left(!(n-1)+!(n-2)\right)$.  You can show the first few cases by hand, and then use induction: if $n$ is odd, then $n-1$ is even, and by the induction hypothesis $!(n-1)$ is odd; likewise, $n-2$ is odd and so by the induction hypothesis, $!(n-2)$ is even and $\bigl(!(n-1)+!(n-2)\bigr)$ is odd, leading to the result that $!n=(n-1)\cdot\bigl(!(n-1)+!(n-2)\bigr) = \mathrm{even}\cdot\mathrm{odd}$ is even.  Similarly, if $n$ is even then $n-1$ is odd and $n-2$ is even, so $!(n-1)$ is even, $!(n-2)$ is odd; then once again $\bigl(!(n-1)+!(n-2)\bigr)$ is odd, and so $!n = (n-1)\cdot \bigl(!(n-1)+!(n-2)\bigr) = \mathrm{odd}\cdot\mathrm{odd}$ is odd.
