Proving an identity involving binomial coefficients I need to prove the following identity:
$$\sum\limits_{j=0}^{n-s}\binom{n-s}{j} (s+j-1)(n-1)^{n-s-j-1}=sn^{n-s-1},$$ where $1\leq s\leq n$ and $n>1$.
This is taken from here. It is suggested to write $j\binom{n-s}{j}=(n-s)\binom{n-s-1}{j-1}$ for $j\geq 1$ and then applying the binomial theorem. However, this seems non-trivial to me. I have made the following steps so far:
\begin{align}
\sum\limits_{j=0}^{n-s}\binom{n-s}{j} (s+j-1)(n-1)^{n-s-j-1}&= \\
(s-1)(n-1)^{n-s-1} + \sum\limits_{j=1}^{n-s}\frac{j}{j}\binom{n-s}{j} (s+j-1)(n-1)^{n-s-j-1}&= \\
(s-1)(n-1)^{n-s-1} + \sum\limits_{j=1}^{n-s}\frac{1}{j}(n-s)\binom{n-s-1}{j-1}1^j(s+j-1)(n-1)^{n-s-j-1}&= \\
(s-1)(n-1)^{n-s-1} + n^{n-s-1}\sum\limits_{j=1}^{n-s}\frac{1}{j}(n-s)(s+j-1)&=\\
(s-1)(n-1)^{n-s-1} + n^{n-s-1}(n-s)^2((s-1)H_{n-s}+n-s)\\
\end{align}
I have also tried to apply the binomial theorem directly, yielding no result:
\begin{align}
\sum\limits_{j=0}^{n-s}\binom{n-s}{j} (s+j-1)(n-1)^{n-s-j-1} &=\\
\frac{1}{n-1}\sum\limits_{j=0}^{n-s}\binom{n-s}{j} (s+j-1)(n-1)^{n-s-j}1^j &=\\
\frac{n^{n-s}}{n-1}\sum\limits_{j=0}^{n-s}(s+j-1)&=\\
\frac{n^{n-s}}{2(n-1)}(n-s+1)(n+s-2)
\end{align}
 A: You're on the right track with the idea of inserting $1^j$. The question is how to deal with the factor $s+j-1$. You can't deal with it the way you tried, simply ignoring it and pretending that you can apply the binomial theorem as if it wasn't there. One way of dealing with it has already been suggested in a comment. Here's another way of dealing with it.
You can treat the constant term and the $j$-dependent separately. For the constant term, you can apply your $1^j$ idea directly:
\begin{eqnarray*}
\sum_{j=0}^{n-s}\binom{n-s}j(s-1)(n-1)^{n-s-j-1}
&=&
\frac{s-1}{n-1}\sum_{j=0}^{n-s}\binom{n-s}j(n-1)^{n-s-j}1^j
\\
&=&
\frac{s-1}{n-1}n^{n-s}\;.
\end{eqnarray*}
For the $j$-dependent term, you can use differentiation:
\begin{eqnarray*}
\sum_{j=0}^{n-s}\binom{n-s}jj\,(n-1)^{n-s-j-1}
&=&
\frac1{n-1}\left.q\frac{\partial}{\partial q}\sum_{j=0}^{n-s}\binom{n-s}{j}(n-1)^{n-s-j}q^j\right|_{q=1}
\\
&=&
\frac1{n-1}\left.q\frac{\partial}{\partial q}(n-1+q)^{n-s}\right|_{q=1}
\\
&=&
\frac{n-s}{n-1}n^{n-s-1}\;.
\end{eqnarray*}
Adding the two parts yields
$$
\frac{s-1}{n-1}n^{n-s}+\frac{n-s}{n-1}n^{n-s-1}=\frac{n^{n-s-1}}{n-1}\left(n(s-1)+n-s\right)=sn^{n-s-1}\;.
$$
A: Here  is   a   small   variation using   the given  hint $j\binom{n-s}{j}=(n-s)\binom{n-s-1}{j-1}$ from  the paper.

We    obtain
  \begin{align*}
\color{blue}{\sum_{j=0}^{n-s}}&\color{blue}{\binom{n-s}{j}(s+j-1)(n-1)^{n-s-j-1}}\\
&=(n-s)\sum_{j=1}^{n-s}\binom{n-s-1}{j-1}(n-1)^{n-s-j-1}\\
&\qquad+(s-1)\sum_{j=0}^{n-s}\binom{n-s}{j}(n-1)^{n-s-j-1}\tag{1}\\
&=\frac{n-s}{n-1}\sum_{j=0}^{n-s-1}\binom{n-s-1}{j}(n-1)^{n-s-j-1}\\
&\qquad+\frac{s-1}{n-1}\sum_{j=0}^{n-s}\binom{n-s}{j}(n-1)^{n-s-j}\tag{2}\\
&=\frac{n-s}{n-1}(1+(n-1))^{n-s-1}+\frac{s-1}{n-1}(1+(n-1))^{n-s}\tag{3}\\
&=\frac{n^{n-s-1}}{n-1}\left((n-s)+(s-1)n\right)\tag{4}\\
&\,\,\color{blue}{=sn^{n-s-1}}
\end{align*}
  and the claim follows.

Comment:


*

*In (1) we split the  sum   and    apply the given hint. We also start with $j=1$ at the left hand sum, since the term with index $j=0$ does not contribute.

*In (2) we shift the index $j$ by one at the left-hand sum and we factor out $\frac{1}{n-1}$ at both sums.

*In (3) we appy the binomial theorem twice.

*In (4) we factor out $\frac{n^{n-s-1}}{n-1}$.
