Proving $\sum_{m=k}^Nm\binom{ m-1}{k-1 }/{\binom N k }=\frac{k(N+1)}{k+1}$

Question

I saw this in a magazine, the writer left the equation up to us to prove. I tried to extract the sum, but I just made it more difficult.

$$\sum \limits_{m=k}^Nm\frac{\binom{ m-1} {k-1 }}{\binom N k }=\frac{k(N+1)}{k+1}$$

Answer 1

Use first the identity $$ m{m - 1 \choose k - 1} = k{m \choose k} $$ to transform the left side to $$ k\cdot \sum_{m=k}^N \frac{{m \choose k }}{{N \choose k}} = \frac{k}{N \choose k}\sum_{m=k}^N {m \choose k} \tag{$\clubsuit$} $$ Then observe that \begin{align} \sum_{m=k}^N{m \choose k} &= {k \choose k } + {k + 1 \choose k } + \cdots + {N \choose k} \\ &= {k + 1 \choose k + 1} + {k + 1 \choose k } + \cdots + {N \choose k} \\ &= {k + 2 \choose k + 1} + {k + 2 \choose k} + \cdots + {N \choose k} \\ &= \cdots \\ &= {N + 1 \choose k + 1} \tag{$\spadesuit$} \end{align} Combining $(\clubsuit)$ and $(\spadesuit)$ would obtain the result.

Answer 2

A combinatorial proof isn’t too hard to find. Rewrite the identity as

$$\sum_{m=k}^Nm\binom{m-1}{k-1}=\frac{k(N+1)}{k+1}\binom{N}k=k\binom{N+1}{k+1}\;.\tag{1}$$

Suppose that you have a set of $N+1$ white balls numbered $0$ through $N$. The righthand side of $(1)$ is the number of ways to perform the following task:

• choose $k+1$ of these balls, and then paint any one of these $k+1$ balls red except the one with the largest number.

In how many ways can we perform this task so that the largest number on any ball in the set is $m$? There are $m$ balls with numbers smaller than $m$, so there are $m$ ways to choose one of them to paint red. Say the red ball is number $k$; our chosen set will contain balls $k$ and $m$, so there are $(k+1)-2=k-1$ balls yet to be chosen for it from the remaining $m-1$ balls with numbers below $m$. This can be done in $\binom{m-1}{k-1}$ ways, so there are altogether $m\binom{m-1}{k-1}$ ways to accomplish the task so that the largest number on any ball in the chosen set is $m$. Clearly $m$ must be at least $k$, since we’re picking $k+1$ balls, and certainly it cannot be more than $N$, so the summation on the lefthand side of $(1)$ covers all possible values of $m$ and therefore also gives us the total number of ways to carry out the task.