1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I add my calculation to question description (as Edit 1). $\endgroup$ – SomeStudent Apr 12 '18 at 15:53
0
$\begingroup$

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

$\endgroup$

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.