I can't understand the equality in equation 4 in this paper.
I understand everything up until that point. I see how $$j \binom{n-p}{j}=(n-s)\binom{n-s-1}{j-1}$$ but I'm not sure how they used that and the binomial identity (I'm not sure which identity they are referring to) to show the equation in eq. 4, that is: $$ \sum_{j=0}^{n-s}\binom{n-s}{j}(s+j-1)(n-1)^{n-s-j-1}=sn^{n-s-1}$$ Can anyone help me understand this last part of their proof? Why is this equation true? Thanks.
Put $n-s-j=r$:
$$\begin{align} \sum_{j=0}^{n-s}\binom {n-s}j(s+j-1)(n-1)^{n-s-j-1} &=\sum_{r=0}^{n-s}\binom{n-s}{n-s-r}(n-r-1)(n-1)^{r-1}\\\\ &=\sum_{r=0}^{n-s}\binom {n-s}r(n-1)^r-\sum_{r=0}^{n-s}\binom {n-s}r r(n-1)^{r-1}\\\\ &=[1+(n-1)]^{n-s}-(n-s)n^{n-s-1}\\\\ &=n^{n-s}-(n-s)n^{n-s-1}\\\\ &=sn^{n-s-1}\quad\blacksquare \end{align}$$
Some additional notes which may be useful in reading the above:
When substituting $n-s-j=r$, notice that when $j=0, r=n-s$ and when $j=n-s, r=0$ so limits are the same (but inverted).
The following identities are useful: $$\sum_{r=0}^m \binom mr x^r=(1+x)^m\\ \sum_{r=0}^{m}\binom mr rx^{r-1}=m(1+x)^{m-1}$$ Substitute $m=n-s$ and $x=n-1$ and the result unfolds before your eyes!