Closed form summation of expression with binomial coefficient I am trying to find a closed form expression of the sum below:
$$ \mathbb{E}(S) = \sum_{s=0}^{N-n} s {N-s-1 \choose n-1} $$
I have considered summation by parts
$$ \sum_{k=m}^n f_k \Delta g_k = f_ng_{n+1} - f_mg_m - \sum_{k=m}^{n-1}g_{k+1}\Delta_k $$
Setting $f_k=s$ and $\Delta g_k = {N-s-1 \choose n-1}$ I remove $s$ from the sum entirely, but this requires guessing an appropriate $g_k$. Is this the right direction to go? 
Ignoring my assumption that summation by parts is possible, are there standard results which can be applied to this sum?
 A: Let us use the identity that $$\sum_{k=0}^{p} {k \choose m}= {p+1 \choose m+1}~~~~(1)$$ Using this let us find
$$\sum_{k=0}^{p} k {k \choose m}=\sum_{k=0}^{p}[ (k+1-1) {k \choose m}= \sum_{k=0}^{p}[(k+1) \frac{k!}{m! (k-m)!}-{k \choose m}]=\sum_{k=0}^{p}[(k+1) \frac{k!}{m! (k-m)!}-{k \choose m}]= \sum_{k=0}^{p}[(m+1) {k+1 \choose m+1}-{k \choose m}]$$
Using )1) we get 
$$\sum_{k=0}^{p} k {k \choose m}= (m+1) {p+2 \choose m+2}-{p+1 \choose m+1}~~~~(2)$$
$$E=\sum_{s=0}^{N-n} s  {N-s-1 \choose n-1} =\sum_{k=n-1}^{N-1} (N-k-1) {k \choose n-1}, ~\text{where}~ N-s-1=k.$$
$$E=\sum_{k=n-1}^{N-1} (N-1) {k \choose n-1}-\sum_{k=n-1}^{N-1} k {k \choose n-1}$$
Using (1) and (2), we get 
$$E=(N-1){N \choose n}-n {N+1 \choose n+1} +{N \choose n}$$
$$E=N {N \choose n}-n {N+1 \choose n+1}$$
Finally $$E={N \choose n+1}$$
as pointed out by @Rob Pratt in the comment below.
A: Maybe for problems like this it's worth trying to prove a slightly easier version and then hope it helps finding a general solution.
For example you could first try to prove that
$$\sum_{s=0}^{N-n}{N-s-1\choose n-1}={N\choose n}$$
And then make some algebraic manipulation. The final answer should be $N\choose n+1$.
There is also a combinatorial interpretation. It's easier to spot once we know the actual answer.
Consider $N$ objects, say $\{x_1,x_2,...,x_N\}$. Then $N\choose {n+1}$ is the number of ways we can pick $n+1$ objects from this set.
This is another way to count it:  
We pick a set of $n+1$ objects the following way; first we choose the object with the second largest index; this must be one of $x_n,...,x_{N-1}$ since there is exactly one object with larger index and $n-1$ objects with lower index. 
Suppose we have picked $x_{N-s}$ with $n\leq N-s\leq N-1$, ie $1\leq s\leq N-n$.
Now we pick the element with largest index. We have $s$ choices: $x_{N-s+1},...,x_N$.
Finally, we choose the remaining $n-1$ objects; these must lie in the set $\{x_1,x_2,...x_{N-s-1}\}$, hence we have ${N-s-1}\choose {n-1}$ choices.
Thus if our first pick is $x_{N-s}$, we have $s{{N-s-1}\choose {n-1}}$ ways to pick the remaining $n$ objects. If we sum over $s$ we get the number of ways we can pick $n+1$ objects from a set of $N$ objects: 
$$\sum_{s=1}^{N-n}s{{N-s-1}\choose {n-1}}={N\choose{n+1}}$$
A: We use    the  coefficient of operator  $[z^n]$  to denote the coefficient  of $z^n$ in a series. This way we can write for instance
\begin{align*}
\binom{n}{k}=[z^k](1+z)^n\tag{1}
\end{align*}

We    obtain for $0\leq n\leq N$:
  \begin{align*}
\color{blue}{\sum_{s=0}^{N-n}}&\color{blue}{s\binom{N-s-1}{n-1}}\\
&=\sum_{s=0}^{N-n}s[z^{n-1}](1+z)^{N-s-1}\tag{2}\\
&=-[z^{n-1}](1+z)^N\frac{d}{dz}\sum_{s=0}^{N-n}(1+z)^{-s}\tag{3}\\
&=-[z^{n-1}](1+z)^N\frac{d}{dz}\frac{(1+z)^{n-N-1}-1}{z}\tag{4}\\
&=-[z^{n-1}](1+z)^N\left(\frac{(n-N-1)(1+z)^{n-N-2}}{z}-\frac{(1+z)^{n-N-1}}{z^2}-\frac{1}{z^2}\right)\tag{5}\\
&=-(n-N-1)[z^n](1+z)^{n-2}+[z^{n+1}](1+z)^{n-1}+[z^{n+1}](1+z)^N\tag{6}\\
&\,\,\color{blue}{=\binom{N}{n+1}}\tag{7}
\end{align*}

Comment:


*

*In (2) we use the coeffcient of operator according to (1).

*In (3) we do some   rearrangements  and write the expression  with the differentiation operator to get rid of the factor $s$.

*In (4) we apply  the finite geometric series formula.

*In (5) we do the differentiation.

*In (6) we simplify and use the rule $[z^{p-q}]A(z)=[z^p]z^qA(z)$.

*In (7) we select the coefficient of $z^{n+1}$ of  the  right-most term observing that the other terms do not contribute.
A: $$
\begin{align}
\sum_{s=0}^{N-n}s\binom{N-s-1}{n-1}
&=\sum_{s=0}^{N-n}\binom{N-s-1}{N-n-s}\binom{s}{s-1}\tag1\\
&=(-1)^{N-n-1}\sum_{s=0}^{N-n}\binom{-n}{N-n-s}\binom{-2}{s-1}\tag2\\
&=(-1)^{N-n-1}\binom{-n-2}{N-n-1}\tag3\\
&=\binom{N}{N-n-1}\tag4\\
&=\binom{N}{n+1}\tag5
\end{align}
$$
Explanation:
$(1)$: symmetry of Pascal's Triangle and $s[s\ge1]=\binom{s}{s-1}$
$(2)$: negative binomial coefficients
$(3)$: Vandermonde's Identity
$(4)$: negative binomial coefficients
$(5)$: symmetry of Pascal's Triangle
