# Show that $\sum_{i=0}^{\log n - 1} \frac{1}{\log n - i} = \Theta(\log\log n)\;.$

$$\sum_{i=0}^{\log n - 1} \frac{1}{\log n - i} = \Theta(\log\log n)$$

Well, my maths skills aren't that good, so other than trying to insert $i=0,1,2,\ldots$ and summing it up didn't help me to get to $\log\log n\,.$ Any ideas?

Edit: maybe somehow taking the $log$ out, and then somehow discovering I have an harmonic series that goes down and its $logn$ too.. But I'm not sure how to implement this..

• Start with the substitution $\log n=\mu$. It should be less confusing that way. – Simply Beautiful Art Sep 17 '16 at 15:09
• Hint: Consider this sum as an approximation of the integral $\int\limits_{0}^{\log n -1}\frac{1}{\log n - x}dx$. – Mihail Poplavskyi Sep 17 '16 at 15:09
• As said above take $\log n = \mu$ and reverse the summation ($i\to \mu - i$) and you are left with $\sum_{i=1}^{\mu}\frac{1}{i}$ the harmonic number (assuming $\log(n)$ here is really $\lfloor \log(n) \rfloor$) – Winther Sep 17 '16 at 15:12
• @Winther That has division by $0$. You mean to start at $i=1$. – Simply Beautiful Art Sep 17 '16 at 15:13

Using the substitution $\log n=\mu$, we get

$$\sum_{i=0}^{\mu-1}\frac1{\mu-i}=\Theta(\log\mu)$$

If we approximate with an integral, we get

$$\sum_{i=0}^{\mu-1}\frac1{\mu-i}\approx\int_0^{\mu-1}\frac1{\mu-t}dt$$

And the rest should be quite clear.

• Thank you. So I do get to a harmonic series to solve this. – Ilan Aizelman WS Sep 17 '16 at 15:14

Let we prove a preliminary lemma first.

Lemma $(1)$ $$H_m = \sum_{k=1}^{m}\frac{1}{k}=\Theta(\log m)$$

Proof. By the concavity of the logarithm function over $\mathbb{R}^+$ we have $$\frac{1}{k}\leq \log\left(k+\frac{1}{2}\right)-\log\left(k-\frac{1}{2}\right)$$ for any $k\geq 1$, hence $H_m \leq \log(2m+1)$ is a consequence of a telescopic sum.
On the other hand, by the convexity of $\frac{1}{x}$ over $\mathbb{R}^+$ we have: $$H_m-\frac{1}{2}-\frac{1}{2m}\geq \int_{1}^{m}\frac{dx}{x}$$ hence $H_m\geq \log(m)+\frac{1}{2}+\frac{1}{2m}$.

We may notice that $$\sum_{0\leq i\leq \log(n)-1}\frac{1}{\log(n)-i}=\sum_{1\leq k\leq \log(n)}\frac{1}{k} = H_{\left\lfloor\log n\right\rfloor}\stackrel{(1)}{=}\Theta\left(\log\left\lfloor\log n\right\rfloor\right)=\color{red}{\Theta\left(\log\log n\right)}.$$