1
$\begingroup$

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.

$\endgroup$

1 Answer 1

2
$\begingroup$

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}

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.