Proving an identity involving binomial coefficients

Question

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}

Answer 1

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}\;. $$

Answer 2

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}$.