As stated, the result is not true, it should be: \[\sum_{j=k}^n (-1)^{n-j} S(n,j) s(j,k) = \sum_{j=k}^n (-1)^{n-j} s(n,j) S(j,k) =\delta_{n,k}\]
First we note that \[\displaystyle\sum_{n\geq 0} S(n,k) \displaystyle\frac{x^n}{n!} = \frac{1}{k!}\cdot\left(\frac{x^1}{1!} + \frac{x^2}{2!}+...\right)^k = \frac{1}{k!}\cdot\left(e^x - 1\right)^k (*)\]
Thus we write \[ A(x) := \displaystyle\sum_{n} \left( \displaystyle\frac{x^n}{n!} \cdot \sum_{j} (-1)^{n-j} S(n,j) s(j,k) \right) = \sum_j \left( \sum_n S(n,j) \cdot \displaystyle\frac{(-x)^n}{n!} \right) \cdot s(j,k) \cdot (-1)^j = \sum_j \frac{\left(1 - e^{-x}\right)^j}{j!} \cdot s(j,k)\]
And on the other hand \[ \sum_{j,k} s(j,k)\cdot \frac{x^j}{j!}\cdot y^k = \exp\left(y\cdot \log\left(\frac{1}{1-x}\right)\right) (**)\]
Thus \[ \sum_j s(j,k) \cdot \frac{x^j}{j!} = \frac{1}{k!}\cdot \log^k\left(\frac{1}{1-x}\right)\]
And \[A(x) = \sum_j \frac{\left(1 - e^{-x}\right)^j}{j!} \cdot s(j,k) = \frac{1}{k!}\cdot \log^k\left(\frac{1}{1-(1 - e^{-x})}\right) = \frac{x^k}{k!} \]
Which indeed implies $\sum_{j=k}^n (-1)^{n-j} S(n,j) s(j,k) =\delta_{n,k}$. $\square$ ( I will leave the other identity to you (Wink) )
For (*), note that the coefficient of $x^n$ in $\frac{1}{k!}\cdot\left(\frac{x^1}{1!} + \frac{x^2}{2!}+...\right)^k $ is actually $ \frac{1}{k!}\cdot \sum_{d_1+...+d_k = n ; d_i > 0} \frac{1}{d_1!\cdot d_2!\cdot ... d_k!} $ , and so if we multiply it by $n!$ we get $ \frac{1}{k!}\cdot \sum_{d_1+...+d_k = n ; d_i > 0} \frac{n!}{d_1!\cdot d_2!\cdot ... d_k!} $ which should ring a bell.
Indeed $\frac{n!}{d_1!\cdot d_2!\cdot ... d_k!}$ is the number of permutations with repetitions, in which you have $n$ elements, $d_1$ of type $1$, etc... so we are actually putting $n$ elements into $k$ (non-empty) boxes. But since what we want are partitions, we don't really care about the renaming of those "boxes", thus the $\frac{1}{k!}$ and $(*)$ is proved.
Now for $(**)$ note that $ \exp\left(y\cdot \log\left(\frac{1}{1-x}\right)\right) = \exp\left(y\cdot \sum_{n\geq 1}{\frac{(n-1)!}{n!}\cdot x^n}\right) = \displaystyle\sum_{k=0}^{\infty}{\frac{1}{k!}\cdot \left(y\cdot \sum_{n\geq 1}{\frac{(n-1)!}{n!}\cdot x^n}\right)^k}$. And here by a similar idea, the coefficient of $x^a y^k$ in $\frac{1}{k!}\cdot \left(y\cdot \sum_{n\geq 1}{\frac{(n-1)!}{n!}\cdot x^n}\right)^k$ corresponds to the number of permutations of $a$ elements into $k$ cycles (remember $(n-1)!$ is the number of cyclic permutations of $n$ elements) , but divided by $a!$.
Some references :
- Analytic Combinatorics by Flajolet and Sedgewick. Page 736 of the book ( page 752 of the pdf available online). States $(*)$ and $(**)$
- Generatingfunctionology by Herbert Wilf. Page 174 exercise 12 is related (in fact you the reader is expected to discover your identities), and $(**)$ appears in page 87 as a result of the theory developed in that chapter.
Both references are freely available online! :D
