<s>[INST] Prove derangement formula by induction I found this in my math book. I have solved a). Exercise b) is to prove the derangement sum by induction.

A derangement of $n$ elements is a permutation where none of the elements keep its original placement. Let $a_n$ be the number of possible derangements of n elements.
a) Show that $a_1=0$, $a_2=1$. Write all the derangements of the elements in $(A,B,C)$ and the elements in $(A,B,C,D)$. Show that the recursion formula is:
$a_n = (n-1)(a_{n-1} + a_{n-2})$

My answer: For placing element $1$ there are $(n-1)$ possibilities. If field $i$ does not take element 1, there is one forbidden element for each field, and there are $a_{n-1}$ possibilities left. If field $i$ does take element $1$, the problem is reduced to $a_{n-2}$. Because of that the formula is $a_n = (n-1)\left(a_{n-1} + a_{n-2}\right)$.

b) Show by induction that:
$a_n=n!\left[1 - \frac{1}{1!} + \frac{1}{2!} -... + (-1)^n\frac{1}{n!}\right]$.

My thoughts: I know how to prove it by the principle of inclusion and exclusion, but not induction. I guess the recursion formula from a) can be used.
 [/INST] It is actually straightforward. It is clear that the formula holds  for 1 and 2. Assume the formula holds for $1 \leq k \leq n $ and show that it holds for $n+1$
\begin{align}
a_{n+1} &= n \cdot (a_n + a_{n-1})\\
&= n \cdot ( n! \cdot [ 1 - \frac1{1!} + \cdots + (-1)^{n} \cdot \frac1{n!}] + (n-1)! \cdot [ 1 - \frac1{1!} + \cdots + (-1)^{n-1} \cdot \frac1{(n-1)!}] )\\
&= n \cdot ( (-1)^n +  (n-1)! \cdot [ 1 - \frac1{1!} + \cdots + (-1)^{n-1} \cdot \frac1{(n-1)!}] \cdot (n+1)) \\
&= n \cdot (-1)^n + n \cdot (n+1) \cdot (n-1)! \cdot [ 1 - \frac1{1!} + \cdots + (-1)^{n-1} \cdot \frac1{(n-1)!}] \\
&= n \cdot (-1)^n + (-1)^n - (-1)^n + (n+1)! \cdot [ 1 - \frac1{1!} + \cdots + (-1)^{n-1} \cdot \frac1{(n-1)!}] \\
&=  (-1)^n \cdot \frac{(n+1)!}{n!}  - (-1)^n + (n+1)! \cdot [ 1 - \frac1{1!} + \cdots + (-1)^{n-1} \cdot \frac1{(n-1)!}] \\
&=  (-1)^n \cdot \frac{(n+1)!}{n!}  + (-1)^{n+1} \cdot \frac{(n+1)!}{(n+1)!}+ (n+1)! \cdot [ 1 - \frac1{1!} + \cdots + (-1)^{n-1} \cdot \frac1{(n-1)!}] \\
&= (n+1)! \cdot [ 1 - \frac1{1!} + \cdots + (-1)^{n+1} \cdot \frac1{(n+1)!}]  \blacksquare \\
\end{align}
</s>