Prove derangement formula by induction

Question

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.

Answer 1

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}