Showing that $\sum\limits_{r=0}^n({1 \over r!} \sum\limits_{s=0}^{n-r}{(-1)^s \over s!}) = 1$

Question

I am trying to show that $n! = \binom{n}{0}D_n + \binom{n}{1}D_{n-1}+...+\binom{n}{n-1}D_1 + \binom{n}{n}D_0$ where $D_k$ is the number of derangements of $k$ objects.

However the last step of my proof requires me to show that

$\sum\limits_{r=0}^n({1 \over r!} \sum\limits_{s=0}^{n-r}{(-1)^s \over s!}) = 1$.

I am completely stuck here as I'm having a difficult time conceptualising the double sum. I know that the the inner sum has a limit of $1 \over e$, and using that information, we could express the limit of the whole thing as

${1 \over e} \sum\limits_{r=0}^\infty {1 \over r!}$.

Now I also know that the limit to the above $\sum\limits_{r=0}^\infty {1 \over r!} = e$.

So by my loose ideas and arguments above the proof could be complete by, ${1 \over e} \cdot e = 1$.

But how can I put these ideas into a more mathematical and solid form?

Answer 1

Your original problem $n! = \binom{n}{0}D_n + \binom{n}{1}D_{n-1}+...+\binom{n}{n-1}D_1 + \binom{n}{n}D_0$ can be solved by noticing that the number of permutations with exactly k fixed points is $\binom{n}{k}D_{n-k}$.

However, your identity $\sum_\limits{r=0}^n({1 \over r!} \sum\limits_{s=0}^{n-r}{(-1)^s \over s!}) = 1$ can be proved routinely by exchanging the order of summation.

Actually, using your original problem and generating function method, one can derive the explicit formula for the number of derangements (the other way is using the inclusive-exclusive formula)

Answer 2

As regards your identity, $$\sum_{r=0}^n({1 \over r!} \sum_{s=0}^{n-r}{(-1)^s \over s!}) = \sum_{r=0}^n\sum_{s=0}^{n-r}{(-1)^{s} \binom{r+s}{r}\over (r+s)!}\\= \sum_{r=0}^n\sum_{m=0}^{n}{(-1)^{m-r} \binom{m}{r}\over m!}=\sum_{m=0}^{n}{(-1)^m\over m!}\sum_{r=0}^m(-1)^{r} \binom{m}{r}= 1+\sum_{m=1}^{n}{(-1)^m\over m!}(1-1)^m=1.$$ However I think that your original problem about derangements can be solved in an easier way.

Answer 3

You have that $\displaystyle \sum_{s=0}^k \frac{(-1)^s}{s!}$ is the coefficient of $x^k$ in the product of $\exp(-x)$ by $\displaystyle \frac{1}{1-x}$. Hence your expression is the coefficient of $x^n$ in the product of $\exp(x)$ by $\displaystyle \frac{\exp(-x)}{1-x}$, i.e it is the coefficient of $x^n$ in $\displaystyle \frac{1}{1-x}$, hence equal to $1$.