I need help in proving an identity about the Inclusion exclusion principle

Question

I need to prove the following identity: $$ 1 = \sum_{k=0}^n \sum_{i=0}^k \frac{(-1)^i}{(n-k)!i!}$$

The solution has to do with the Inclusion exclusion principle.

Answer 1

HINT: Recall $[n]=\{1,2,\cdots ,n\}.$ Consider $S_n=\{\pi:[n]\longrightarrow [n]:\pi \text{ bijection}\}.$ You know that $|S_n|=n!$. Consider the following sets: $$A_k = \{\pi \in S_n: \sigma(\pi)=k\},$$ where $\sigma (\pi)=|\{i\in [n]:\pi _i \neq i\}|.$
Compute the cardinals of those sets and express the whole $S_n$ in terms of those sets.
Can you finish? If not, let me know.
Edit: Sure, so $S_n=\bigcup _{k=0}^nA_k,$ and because $A_i\cap A_j = \emptyset,$ then $$n!=|S_n|=\sum _{k=0}^n|A_k|.$$ To compute $A_k, $ notice that we have to choose the $k$ spots to have that $\pi _i \neq i,$ so in those $k$ spots we have a derangement. The number of derangements on a $k$ permutation can be founded using inclusion-exclusion and i am gonna denoted it by $D_k.$ So $|A_k|=\binom{n}{k}|D_k|.$
To compute $D_k$ notice that a derangement is a permutation without fix points, and hence $D_k=S_k\setminus \bigcup _{i=1}^kB_i,$ where $B_i =\{\pi \in S_k:\pi _i = i\}.$ Then, by inclusion exclusion $$|D_k|=k!-\sum _{i = 1}^k(-1)^{i-1}\sum _{X\in \binom{[k]}{i}}|\bigcap _{y\in X}B_y|.$$ It is clear that $$|B_y|=(k-1)!,|B_y\cap B_z|=(k-2)!..$$ and then $$|D_k|=k!-\sum _{i = 1}^k(-1)^{i-1}\sum _{X\in \binom{[k]}{i}}(k-i)!=\sum _{i = 0}^k(-1)^{i}\binom{k}{i}(k-i)!=k!\sum _{i = 0}^k(-1)^{i}\frac{1}{i!}.$$ Then, $$n!=\sum _{k = 0}^n|A_k|=\sum _{k = 0}^n\binom{n}{k}\left ( k!\sum _{i = 0}^k\frac{(-1)^{i}}{i!} \right )=\sum _{k = 0}^n\frac{n!}{(n-k)!}\left ( \sum _{i = 0}^k\frac{(-1)^{i}}{i!} \right ),$$ and the identity follows by cancelling the $n!$