3
$\begingroup$

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!

$\endgroup$
2
  • 1
    $\begingroup$ Hint: Show that $\ln x$ and $\sum\frac{1}{i}$ differ by at most a constant. $\endgroup$
    – Element118
    Dec 7, 2015 at 13:13
  • 5
    $\begingroup$ $\sum_{k=1}^n \frac 1 k$ is between a lower and an upper Riemann sum for $\int_1^{n+1} \frac 1 x \rm{d}x$. $\endgroup$
    – BrianO
    Dec 7, 2015 at 13:14

2 Answers 2

6
$\begingroup$

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$

$\endgroup$
2
$\begingroup$

$$\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$$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .