Tight asymptotic upper bound of $\sum\limits_{k=2}^N \frac{k}{\log k}$

1.1k Views Asked by At

I'd like to find an asymptotic bound for $$\sum_{k=2}^N \frac{k}{\log k}$$

Trivially, for $k > 3$, each term is less than $\frac{N}{\log N}$, thus $$\sum_{k=2}^N \frac{k}{\log k} = \mathcal{O}\left(\frac{N^2}{\log N}\right)$$

The bound seems not tight. Can we be more precise?

1

There are 1 best solutions below

0
On BEST ANSWER

If we apply summation by parts we get $$ \sum_{k=2}^{N}\frac{k}{\log k} = \frac{N^2+N-2}{2\log N} +\sum_{k=2}^{N-1}\frac{k^2+k-2}{2}\left(\frac{1}{\log k}-\frac{1}{\log(k+1)}\right)$$ from which: $$ \sum_{k=2}^{N}\frac{k}{\log k} \leq \frac{N^2+N-2}{2\log N} + \sum_{k=2}^{N-1}\frac{k+1}{2\log^2 k} $$ and your sum is indeed $O\left(\frac{N^2}{\log N}\right)$, but such bound is sharp.