$\sum_{k=1}^{n} \frac{k}{k !} \sum_{i=0}^{n-k} \frac{(-1)^{i}}{i !}=1$

Question

Prove that

$\sum_{k=1}^{n} \frac{k}{k !} \sum_{i=0}^{n-k} \frac{(-1)^{i}}{i !}=1$

There were no significant progress on the task.

Answer 1

Negative signs and fractions are not great for combinatorial proofs. Fortunately, the inner summation can be replaced with a single positive quantity, since it is $1/(n-k)!$ times the familiar formula for the number of derrangements of an $(n-k)$ element set. This gives $$ \sum_{k=1}^{n} \frac{k}{k !} \sum_{i=0}^{n-k} \frac{(-1)^{i}}{i !}=\sum_{k=1}^n k\cdot \frac{1}{k!(n-k)!} D_{n-k} =\frac1{n!}\sum_{k=1}^n k\cdot \binom{n}kD_{n-k}=1, $$ so you can equivalently prove $$ \sum_{k=1}^nk\cdot \color{blue}{\binom{n}kD_{n-k}}=n! $$ Note that $ \color{blue}{\binom{n}kD_{n-k}}$ is the number of permutations of an $n$ element set with exactly $k$ fixed points (choose the fixed points in $\binom{n}k$ ways, then derange the remaining $n-k$ elements). Therefore, this summation counts the number of ways to choose a permutation of $n$ elements, with some number $k$ of fixed points, and then select one of its fixed points in $k$ ways. In other words, the LHS counts the set $$ \{(\pi,j):\pi\text{ is a permutation of $\{1,\dots,n\}$},j\text{ is a fixed point of $\pi$}\} $$ So all you need to do is prove the number of such ordered pairs is $n!$. There is a very quick proof of this.