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?
 A: \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}.$$
A: $$\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}$$
