Prove ln(n) diverges as quickly as the harmonic series.

Question

Question: Find a (simple) $f(n)$ so that $\lim\limits_{n \rightarrow \infty} \frac{n \sum\limits_{k=1}^{n} \frac{1}{k}}{f(n)} = 1$

My Attempt: I know the answer, by using Mathematica, is $f(n) = n \cdot ln(n)$. I, however, can't find a way to prove this. I've only tried $$\lim\limits_{n \rightarrow \infty} ln(n) = \int\limits_{1}^{\infty} \frac{1}{x} \ dx \approx \sum\limits_{k=1}^{\infty} \frac{1}{k} = \lim\limits_{n \rightarrow \infty} \sum\limits_{k=1}^{n} \frac{1}{k}$$ But that doesn't seem entirely correct. Does anybody know a way to prove this limit?

Thanks in advance!

Answer 1

Let, $H_n=\sum \limits_{i=1}^n \frac{1}{i}$

$\ln(n)=\int \limits_{1}^n \frac{1}{x}~dx=\sum \limits_{i=1}^{n-1} \int \limits_{i}^{i+1} \frac{1}{x}~dx\le \sum \limits_{i=1}^{n-1} \int \limits_{i}^{i+1} \frac{1}{i}~dx=H_{n-1}$

Similarly, $\ln(n)=\int \limits_{1}^n \frac{1}{x}~dx=\sum \limits_{i=1}^{n-1} \int \limits_{i}^{i+1} \frac{1}{x}~dx \ge \sum \limits_{i=1}^{n-1} \int \limits_{i}^{i+1} \frac{1}{i+1}~dx=H_{n}-1$

So, $\ln(n+1) \le H_n \le \ln(n)+1 \implies \frac{H_n}{\ln(n)} \to 1$ as $n \to \infty$

Answer 2

$$\sum_{k=1}^n \frac1k=1+\int_2^{n+1}\frac1{\lfloor x\rfloor}dx$$ $$x-1<\lfloor x\rfloor\le x$$ $$1+\int_2^{n+1}\frac1{x}dx\le1+\int_2^{n+1}\frac1{\lfloor x\rfloor}dx<1+\int_2^{n+1}\frac1{x-1}dx$$ $$\ln(n+1)-\ln2+1 \le\sum_{k=1}^n \frac1k<\ln n + 1$$ $$\lim_{n\to\infty}\frac{\ln(n+1)-\ln2+1}{\ln n} \le\lim_{n\to\infty}\frac{\sum_{k=1}^n \frac1k}{\ln n}<\lim_{n\to\infty}\frac{\ln n + 1}{\ln n}$$ $$1 \le\lim_{n\to\infty}\frac{\sum_{k=1}^n \frac1k}{\ln n}\le1$$ $$\therefore\lim_{n\to\infty}\frac{n\sum_{k=1}^n \frac1k}{n\ln n}=1$$