Closed form summation of expression with binomial coefficient

Question

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?

Answer 1

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.

Answer 2

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

Answer 3

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.

Answer 4

$$ \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