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


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

  • $\begingroup$ 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}$?" $\endgroup$ – hengxin May 3 '18 at 13:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.