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})$.
I'm not so sure about this bound. What is a good way to approach this problem?
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)$.