I have derived two different solutions to the same problem involving computing the expected time to find $k$ swaps when collecting coupons. However to me the two sums, although apparently numerically identical, look completely unrelated. Is there some elementary way of showing the following identity? $$\sum_{s=1}^n(s+m) \binom{n}s \sum_{i=0}^s(-1)^i\binom{s}i \left(\frac{s-i}n\right)^{s+m-1}\frac{s}n=n + m - \sum_{k=1}^{n} k^{k-1} \binom{n}{k} \frac{(n-k)^{n+m-k}}{n^{n+m-1}} $$
This is defined for integers $n,m \geq 1$.
This is related to a possibly simpler previous question I asked.