I am currently studying a distributed systems lecture. I came across a relation which I was somewhat confused by.
It states that the following equation
$$ 1+ \sum_{r=2}^n \frac{(n-1)(1)}{(n)(r-1)} $$
is upper bounded ≤ by the harmonic number
$$ 1+H_n=1 + \sum_{i=1}^{n-1} \frac{1}{i} $$
The reason is that the fraction $$\frac{(n-1)}{n}$$ is always smaller than 1
Can someone give me more intuition on why does that holds true? Or when can you upper bound a summation by the harmonic number?
Thank you!
If $r\in\{2,3,\ldots,n\}$, then$$\frac{n-1}{n(r-1)}=\frac{n-1}n\times\frac1r<\frac1r$$ and therefore\begin{align}1+\sum_{r=2}^n\frac{n-1}{n(r-1)}&<1+\sum_{r=2}^n\frac1{r-1}\\&=1+\sum_{r=1}^{n-1}\frac1r\\&=1+H_{n-1}.\end{align}