0
$\begingroup$

What is upper bound of sum $n \sum_{k=1}^n \frac1k$ . Is it $O(n\log n)$ (i.e sum is bounded by $c\cdot n\log n$ for some constant $c$ and for all $n \ge n_0$) ? How to prove it ?

$\endgroup$
2
$\begingroup$

We have $$n\sum_{k=1}^n\frac 1k\le n\cdot\left(1+ \sum_{k=2}^n\int_{k-1}^k\frac {\mathrm dx}x\right)=n\left(1+\int_1^n\frac {\mathrm dx}x\right)=n(1+\ln n)<2n\ln n$$ for all $n>e$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ +1. very nice. Is there any relationship between you and this famous double? I have never seen two contributors with the same tags here... $\endgroup$ – gt6989b Jan 21 at 15:08
0
$\begingroup$

HINT

Look at Harmonic numbers and note that the partial sums $H_n = \sum_{k=1}^n \frac1k$ can be approximated by $\ln n + \gamma$, where $\gamma$ is the Mascheroni constant.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy