# Not able to simplify a sum over reciprocals of $\log i$

Every time I solve these questions, I get stuck at the end where I need to find a closed form for the summation.

Here in this case, I have reached until this point: \begin{align} T(n) &= T(n-2) + 1/\lg n \\ &= T(n-4)+ 1/\lg(n-2) + 1/\lg n \\ &= T(n-6) + 1/\lg(n-4) + 1/\lg(n-2) + 1/\lg n. \qquad (1) \end{align} Assuming $T(1) = 1$, I put $n - 6 = 1$ and substituted into (1):

$$T(6) = T(1) + 1/\lg3+ 1/\lg 5+ 1/\lg7.$$

Now at this point I am not able to find out $\sum_{i=1}^n 1/\lg(2i-1)$.

On similar grounds , I become blank for another recurrence relation $T(n) = T(n-1)+1/\lg n$, and my solution drills down up to here: $$T(n) = T(1)+ 1/\lg2 + 1/\lg3 + 1/\lg4 + \cdots.$$

How do I evaluate such sums?

• Please read your question after posting it, and try to edit it so that it shows up correctly. Use LaTeX if possible. – Yuval Filmus Apr 24 '14 at 0:40
• "summation has to be converted to a formula and that becomes the running time of the algorithm." -- no sum suddently becomes the running time. I don't know whether this weird choice of words is an actual misconception or just a language issue. – Raphael Apr 24 '14 at 6:28
• I suggest you check out our reference question on solving recurrences; there are more methods available that involve less guessing. (Note that you also need an induction proof to verify your guess.) – Raphael Apr 24 '14 at 6:29
• Further to Raphael's comment, a recurrence is just a way of specifying a function and that function could be used to measure literally anything, in just the same way that numbers can be used to measure anything. – David Richerby Apr 24 '14 at 9:01

## 1 Answer

The trick to evaluate these sums is integration. We have the following very useful inequality for a non-decreasing $f(i)$: $$\int_0^n f(x) dx \leq \sum_{i=1}^n f(i) \leq \int_1^{n+1} f(x) dx.$$ In your case, $f(i)$ is in fact non-increasing, and in that case we have $$\int_1^{n+1} f(x) dx \leq \sum_{i=1}^n f(i) \leq \int_0^n f(x) dx.$$ For example, we can estimate $$\int_2^{n+1} \frac{dx}{\log x} \leq \sum_{i=2}^n f(i) \leq \int_1^n \frac{dx}{\log x}.$$ Unfortunately, the antiderivative of $1/\log x$ is not an elementary function, but is known as the logarithmic integral $li(x)$. Asymptotically, $li(x) \sim x/\log x$, and so we deduce $$\sum_{i=2}^n \frac{1}{\lg i} = \Theta\left(\frac{n}{\log n}\right).$$ In this particular case, we can obtain these bounds directly. Since $1/\lg i \geq 1/\lg n$, we obtain a lower bound of $(n-1)/\lg n$. Conversely, for $i \geq \sqrt{n}$ we have $1/\lg i \leq 1/\lg \sqrt{n} = 2/\lg n$, and so $$\sum_{i=2}^n \frac{1}{\lg i} \leq \sqrt{n} \lg 2 + n \frac{2}{\lg n} = O\left(\frac{n}{\lg n}\right).$$ If you want to obtain better estimates on such sums, the way to go is Euler–Maclaurin summation, which can be used to obtain an asymptotic series for $\log n!$, for example.