# How to solve $T(n)= T(n - 1) + \frac{1}{n\log n}$?

I am interested in the asymptotic bounds of the following recurrence:

$$T(n)= T(n - 1) + \frac{1}{n\log n}$$

with base case $$T(1) = 1$$. I'm having trouble while solving this recurrence. It seems much more tricky than I initially thought.

I've tried out by iterative method and since $$\log(n!) = n\log n$$, I've got $$\frac{1}{n\log n}$$.

At this point, I've got that the summation of $$\frac{1}{i}$$ is equal to $$\Theta(\log n + O(1))$$. So at the end, I've come up with this bound (by simplifying the two terms): $$\Theta(\frac{1}{n})$$.

We have $$T(n) = \sum_{m=3}^n \frac{1}{m\log m} + T(2).$$ We can bound $$\int_3^{n+1} \frac{dx}{x\log x} \leq \sum_{m=3}^n \frac{1}{m\log m} \leq \int_2^n \frac{dx}{x\log x}.$$ Since $$(\log\log x)' = \frac{1}{x\log x}$$, this shows that $$\log\log(n+1) - \log\log 3 \leq \sum_{m=3}^n \frac{1}{m\log m} \leq \log\log n - \log\log 2,$$ and so $$T(n) = \log\log n + \Theta(1)$$.
• In fact, $\log\log(n+1)-\log\log n$ is decreasing, since $(\log \log x)' = 1/x\log x$ is decreasing. You can check it for concrete values of $n$ Commented Mar 3, 2021 at 11:59