How to calculate this sum with binomials?

Question

In this paper An Improved Algorithm for Decentralized Extrema-Finding in Circular Configurations of Processes from 1979, in chapter with analyze of average number of passes messages I found this equation:

$$\sum_{i=k}^{n-1}k \frac{{i-1}\choose{k-1}}{{n-1}\choose{k-1}} \times \frac{n-i}{n-k} = \frac{n}{k+1}$$

WolframAlpha solution.

Can anyone explain me why it's equal and how can I calculate it?

In paper they write only that this left side "can be simplified to" right side.

Edit 1: I think that main problem is to understand what this sum is: $$\sum_{i=k}^{n-1} {{i-1}\choose{k-1}} \times (n-i)$$ WolframAlpha.

Because:

$$\sum_{i=k}^{n-1}k \frac{{i-1}\choose{k-1}}{{n-1}\choose{k-1}} \times \frac{n-i}{n-k} = \frac{k}{{{n-1}\choose{k-1}}(n-k)} \sum_{i=k}^{n-1} {{i-1}\choose{k-1}} \times (n-i)$$

And according to WolframAlpha: $$\sum_{i=k}^{n-1} {{i-1}\choose{k-1}} \times (n-i) = \frac{n(n-k){{n-1}\choose{k-1}}}{k(k+1)} $$

So everything could be nicely reduced.

Answer 1

Have you seen this formula, sometimes known as the hockey-stick formula $$\sum_{i=k}^{n-1}{i-1\choose k-1}={n-1\choose k}$$ It is proved by identifying the binomial coefficients in Pascal's triangle, noting that ${k-1\choose k-1}={k\choose k}$, and cascading down the diagonal.

Another relevant formula is $i{i-1 \choose k-1} = k{i\choose k}$. Put them together and you get $$(n-i){i-1\choose k-1} = n{i-1\choose k-1} - k{i\choose k}$$ then sum them up separately.

Answer 2

Not a complete solution \begin{align} \sum_{i=k}^{n-1}k \frac{{i-1}\choose{k-1}}{{n-1}\choose{k-1}} \times \frac{n-i}{n-k} &= \sum_{i=k}^{n-1} k\frac{(i-1)!(k-1)!(n-k)!~}{(k-1)!(i-k)!(n-1)!} \times \frac{n-i}{n-k}\\ &= \sum_{i=k}^{n-1} k\frac{(i-1)!(n-k-1)!(n-i)}{(i-k)!(n-1)!} \\ &= k \cdot \frac{(n-k-1)!}{(n-1)!} \cdot\sum_{i=k}^{n-1} \frac{(i-1)!(n-i)}{(i-k)!} \\ \end{align} I'm not sure where to proceed from here, either.

Answer 3

$$\begin{align} \sum_{i=k}^{n-1}\color{orange}{\binom {i-1}{k-1}(n-i)} &=\sum_{i=k}^{n-1}\sum_{j=i}^{n-i}\binom{i-1}{k-1}\\ &=\sum_{j=k}^{n-1}\sum_{i=k}^j\binom {i-1}{k-1}\\ &=\sum_{j=k}^{n-1}\binom jk\\ &=\binom n{k+1}\\ &=\frac 1{k+1}\binom {n}{k}\frac{n-k}1\\ &=\frac {\color{red}n}{\color{red}{(k+1)}\color{blue}k}\color{green}{\binom {n-1}{k-1}}\frac{\color{green}{n-k}}1\\ \sum_{i=k}^{n-i}\color{blue}k\frac {\displaystyle\color{orange}{\binom{i-1}{k-1}}}{\displaystyle\color{green}{\binom {n-1}{k-1}}}\cdot \frac {\color{orange}{n-i}}{\color{green}{n-k}}&= \color{red}{\frac n{k+1}}\qquad\color{red}\blacksquare \end{align}$$