<s>[INST] 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?
 [/INST] \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}.$$
</s>