# 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.

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}