Problem:
Prove that $$s(n)=\sum_{i=1}^n\frac{\log i}{i} = \Theta(\log^2n)$$.
I was able to prove the upper bound with $s(n) \le H_n\log n$, where $H_n = 1 + \frac{1}{2} + ... +\frac{1}{n}$, the harmonic series, and $H_n = \Theta(\log n)$. Can the lower bound achievable using the same technique?
If $x>e$, then the quantity $f(x)=\frac{\ln(x)}{x}$ is decreasing when $x$ increases. We thus have the following inequalities for sufficiently big integer $i$ :
$$ \int_{i}^{i+1} \frac{\ln(t)}{t} dt \leq \frac{\log i}{i} \leq \int_{i-1}^{i} \frac{\ln(t)}{t} dt$$ Therefore if we just keep the $i\geq4$ (so that we always integrate on an interval where the function is decreasing), we can sum the inequalities from $i=4$ to $i=n$ :
$$ \sum_{i=4}^n \int_{i}^{i+1} \frac{\ln(t)}{t} dt \leq\sum_{i=4}^n \frac{\log i}{i} \leq\sum_{i=4}^n \int_{i-1}^{i} \frac{\ln(t)}{t} dt$$ $$ \int_{4}^{n+1} \frac{\ln(t)}{t} dt \leq\sum_{i=4}^n \frac{\log i}{i} \leq \int_{3}^{n} \frac{\ln(t)}{t} dt$$ $$ \frac{1}{2}(\ln(n+1)^2 - \ln(4)^2) \leq\sum_{i=4}^n \frac{\log i}{i} \leq \frac{1}{2}(\ln(n)^2 - \ln(3)^2) $$ From there you should be able to derive both an upper bound and a lower bound asymptotically since the sum in the middle is equal to $s(n)$ up to an additive constant which is independent of $n$.