Not understanding step in Karger Algorithm: How to simplify a long product

I'm reading a book on Randomized Algorithms by Raghawan and Motwani and I don't understand the algebra/calculus of a step in the analysis of Karger's algorithm(Randomized min-cut).

They have the following: $$Pr[\cap_{i=1}^{n-2} E_{i}] \geq \Pi_{i=1}^{n-2}(1-\frac{2}{n-i+1}) = \frac{2}{n(n-1)}$$

This part in particular: $$\Pi_{i=1}^{n-2}(1-\frac{2}{n-i+1}) = \frac{2}{n(n-1)}$$ is hard for me to see when i try to write it out. I know that for example

$$1 + 2 + 3 + 4 + \ldots + n = \frac{n(n+1)}{2}$$ which can be figured out by adding two series together. But I actually don't know a lot about long products like $$\Pi_{i=1}^{n-2}(1-\frac{2}{n-i+1})$$ is there any good place to start if I had to find $$\frac{2}{n(n-1)}$$ ?

1 Answer

\begin{align*} \prod_{i=1}^{n-2} \left( 1-\frac{2}{n-i+1} \right) &= \prod_{i=1}^{n-2} \frac{n-i-1}{n-i+1} \\ &= \frac{\color{red}{n-2}}{n} \cdot \frac{\color{blue}{n-3}}{n-1} \cdot\frac{n-4}{\color{red}{n-2}} \cdot \frac{n-5}{\color{blue}{n-3}} \cdots \frac{\color{purple}{4}}{6} \cdot \frac{\color{green}{3}}{5} \cdot \frac{2}{\color{purple}{4}} \cdot \frac{1}{\color{green}{3}}\\ & = \frac{2}{n(n-1)}. \end{align*}

Where we used the fact that the product is telescopic. Notice how, after simplifying, the only surviving terms from the numerators are $$2$$ and $$1$$ while the only surviving terms from the denominators are $$n$$ and $$n-1$$.

• Thanks for the answer. So the denominator $n(n-1)$ comes from the first two terms where $n$ and $n-1$ does not get cancelled, and then the $2$ and $1$ for the enumerator survives from the last 2 terms and everything else gets cancelled out? Oct 4, 2021 at 22:26
• Exactly.$\phantom{}$ Oct 4, 2021 at 22:29