How to prove $\sum_{i=2}^{n-1}\frac{6(i-1)(n-i)}{n(n-1)(n-2)}=1$?

Question

I am working on a problem of median of 3 quicksort. Any element $2 \leq i \leq n-1$ in the array has a probability of $p_i=\frac{6(i-1)(n-i)}{n(n-1)(n-2)}$ being chosen as a pivot. So, if we sum up all the probabilities, they should equal to 1. Now, how to prove $\sum_{i=2}^{n-1}\frac{6(i-1)(n-i)}{n(n-1)(n-2)}=1$?

Answer 1

Hint

Rewrite $$\sum_{i=2}^{n-1}\frac{6(i-1)(n-i)}{n(n-1)(n-2)}=\frac{6}{n(n-1)(n-2)}\sum_{i=2}^{n-1}(i-1)(n-i)$$ Now $$\sum_{i=2}^{n-1}(i-1)(n-i)=(n+1)\sum_{i=2}^{n-1}i-n \sum_{i=2}^{n-1}1- \sum_{i=2}^{n-1}i^2$$

Answer 2

Put i = r+1, Summation will change from 1 to n-2 and numerator will change to r(n-r-1), now use summation of 1st n natural numbers, sum of square of 1st n natural numbers, simplify it u will have your result.

Answer 3

$$\begin{align} \sum_{i=2}^{n-1}\frac {6(i-1)(n-i)}{n(n-1)(n-2)} &=\frac 6{n(n-1)(n-2)}\sum_{i=1}^{n-2}i(n-i-1)\\ &=\frac {3!}{n(n-1)(n-2)}\sum_{i=1}^{n-2}\sum_{j=i}^{n-2}i\\ &=\frac 1{\binom n3}\sum_{j=1}^{n-2}\sum_{i=1}^j i &&(1\le i\le j\le n-2)\\ &=\frac 1{\binom n3}\sum_{j=1}^{n-2}\binom {j+1}2\\ &=\frac 1{\binom n3}\binom n3\\ &=1\quad\blacksquare \end{align}$$