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

Question

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

Answer 1

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.

Answer 2

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)}. $$