Fixed-point-free permutations An $i \in [n]$ is called a fixed point of a permutation $\sigma \in S_n$ if $\sigma(i) = i$.
Let $D(n)$ be the number of permutations $\sigma \in S_n$ without any fixed point.

Prove that

i) $D(n) = n \cdot D(n-1) + (-1)^n$ for $n \geq 2$
ii) $D(n) = (n-1)(D(n-1) + D(n-2))$ for $n \geq 3$


First I tried to write down all fixed point-less permutations (in one-line notation):
$n \leq 1 \rightarrow$: none
$n = 2$: (2 1)
$n = 3$: (2 3 1) (3 1 2)
$n = 4$ (2 1 4 3) (2 3 4 1) (2 4 1 3) (3 1 4 2) (3 4 1 2) (3 4 2 1) (4 1 2 3) (4 3 1 2) (4 3 2 1)
Unfortunately I didn't find any way of constructing these permutations by using the ones from $(n-1)$.
Could you please help me a little bit?
Thank you in advance!

These are called derangements.  For a discussion, please see for example 
http://en.wikipedia.org/wiki/Derangement
