# How to evaluate this binomial sum?

I come across the following binomial sum when studying the average-case time complexity of an algorithm:

$$\sum_{i = 1}^{n-k+1} i \binom{n-i}{k-1}$$

How to evaluate this sum?

\begin{align} \sum_{i=1}^{n-k+1}i\binom {n-i}{k-1} &=\sum_{i=1}^{n-k+1}\sum_{j=1}^i\binom {n-i}{k-1}\\ &=\sum_{j=1}^{n-k+1}\sum_{i=j}^{n-k+1}\binom {n-i}{k-1} &&\qquad\scriptsize(1\leqslant j\leqslant i\leqslant n-k+1)\\ &=\sum_{j=1}^{n-k+1}\sum_{r=k-1}^{n-j}\binom r{k-1} &&\qquad\scriptsize(r=n-i)\\ &=\sum_{j=1}^{n-k+1}\binom {n-j+1}k\\ &=\sum_{m=k}^n\binom mk &&\qquad\scriptsize(m=n-j+1)\\ &=\color{red}{\binom {n+1}{k+1}}\end{align}
$$r \binom{r-1}{k-1} = k \binom{r}{k}$$ and $$\sum_{0 \le k \le n} \binom{k}{m} = \binom{n+1}{m+1}.$$
• A follow-up question is "Is there a nice combinatoric proof/explanation of this equality $\sum_{i = 1}^{n-k+1} i \binom{n-i}{k-1} = \binom{n+1}{k+1}$?" – hengxin May 3 '18 at 13:21