Prove that $\forall\ n \in \mathbb{N}$ , $$\sum_{k=1}^n (-1)^k\; k!\; S(n,k) = (-1)^n.$$ Give a combinatorial proof and don't use the identity $$x^n = \sum_{k=0}^n S(n,k)(x)_k$$ where $$(x)_k = x(x−1)(x−2)\cdots (x−k+1)$$
Proof:
Recall that $S(n,k)$ is debited as the number of partitions of $[n]$ into $k$ nonempty boxes, where $S(n,k)$ denotes a the Stirling number of the second kind.
Where we have that $S(n,k) = S(n-1,k-1) + k \; S(n-1,k)$.
Then we will prove by induction that $\forall n \in N$ , $$\sum_{k=1}^n (-1)^k\; k!\; S(n,k) = (-1)^n\tag{*}$$
To see this we show the following steps
Base Case:
When $n = 1$, we clearly have $-1 = -1$, which is equal and so the this is true for $n=1$.
Inductive step:
Let $n \in N$ be given and suppose $(*)$ is true for $n$. Then we want to show it's true for $n+1$.
Then By induction: $$ \sum_{k=1}^{n+1}(-1)^{k}k!\left\{n+1 \atop k\right\}= \sum_{k=1}^{n+1}(-1)^{k}k!\left\{n \atop k-1\right\}+\sum_{k=1}^{n+1}(-1)^{k}k!\left\{n \atop k\right\}k=$$
$$ =\sum_{k=1}^{n}(-1)^{k}k!\left\{n \atop k\right\} -(-1)^n (n+1)!+ \sum_{k=1}^{n+1}(-1)^{k}k!\left\{n \atop k\right\}k=$$ = $-(-1)^n (n+1)!+\sum_{k=1}^{n}(-1)^{k}k!\left\{n \atop k\right\}+\sum_{k=1}^{n+1}(-1)^{k}k!\left\{n \atop k\right\}k$ .
basically after this, I am stuck.
However I am having trouble simplifying. Can someone please help me with the inductive step. Thank you. I am also learning the inclusion-exclusion principle. I don't know if I could apply this. But I was thinking to prove it in an inductive way .
By induction: $$ \sum_{k=1}^{n+1}(-1)^{k}k!\left\{n+1 \atop k\right\}= \sum_{k=1}^{n+1}(-1)^{k}k!\left\{n \atop k-1\right\}+\sum_{k=1}^{n+1}(-1)^{k}k!\left\{n \atop k\right\}k=$$ $$ =-\sum_{k=1}^{n}(-1)^{k}(k+1)!\left\{n \atop k\right\}+\sum_{k=1}^{n+1}(-1)^{k}k!\left\{n \atop k\right\}k=$$ $$ =-\sum_{k=1}^{n}(-1)^{k}k!\left\{n \atop k\right\}k-\sum_{k=1}^{n}(-1)^{k}k!\left\{n \atop k\right\}+\sum_{k=1}^{n+1}(-1)^{k}k!\left\{n \atop k\right\}k=-(-1)^{n} $$ I left the details to you.