How to evaluate this binomial sum?

Question

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?

Answer 1

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

Answer 2

\begin{align*} \sum_{i=1}^{n-k+1} i \binom{n-i}{k-1} &= \sum_{i=0}^{n-k} (i+1) \binom{n-i-1}{k-1} \\ &= \sum_{i=0}^{n-k} \big((n+1) - (n-i)\big) \binom{n-i-1}{k-1} \\ &= \sum_{i=0}^{n-k} (n+1) \binom{n-i-1}{k-1} - \sum_{i=0}^{n-k} (n-i) \binom{n-i-1}{k-1} \\ &= (n+1) \sum_{i=0}^{n-k}\binom{n-i-1}{k-1} - k \sum_{i=0}^{n-k} \binom{n-i}{k} \\ &= (n+1) \sum_{m=k-1}^{n-1}\binom{m}{k-1} - k \sum_{m=k}^{n} \binom{m}{k} \\ &= (n+1) \binom{n}{k} - k \binom{n+1}{k+1} \\ &= \binom{n+1}{k+1} \end{align*}

It uses

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