1
$\begingroup$

I have recently learned about asymptotical equivalence, defined as $$ a(n) \sim b(n) \Leftrightarrow \lim\limits_{n \to \infty} \frac{a(n)}{b(n)} = 1$$

Now I would need to prove that $H_n \sim \ln(n)$ where $H_n = \sum_{i=1}^n \frac{1}{i}$ is the harmonic series and $\ln(n)$ is the natural logarithm, but I have no idea how to get started.

I wrote down the definition as \begin{align} \lim\limits_{n \to \infty} \frac{H_n}{\ln(n)} & = \lim\limits_{n \to \infty} \left(\frac{1}{\ln(n)} \cdot \sum_{i=1}^n \frac{1}{i}\right) \\ \end{align} and tried to apply l'Hospital's rule which leads to $\lim\limits_{n \to \infty} \left(\frac{-1}{n\ln^2(n)} \cdot \sum_{i=1}^n \frac{-1}{i^2}\right)$, but that does not seem to be helping me any further. I tried out some other things, but everything seemed to be incorrect or not helpful.

I am looking at it for quite some time now already and I also tried to find some hints online, but I just don't seem to find anything that uses this definition. I must admit I am not really the biggest hero in analysis or calculus, but if anyone could guide me in (one of) the right directions to get to a solution that would already be very helpful. Thanks in advance.

$\endgroup$
  • 1
    $\begingroup$ L'Hopital's rule won't work here because a sum is a discrete sequence and therefore has no derivative. However, there is a "discrete L'Hopital's rule" which works here. That's what Jack uses in his answer below. $\endgroup$ – Antonio Vargas Apr 9 '16 at 15:54
3
$\begingroup$

By the Stolz-Cesàro theorem, $$ \lim_{n\to +\infty}\frac{H_n}{\log n} = \lim_{n\to +\infty}\frac{H_{n+1}-H_{n}}{\log(n+1)-\log n} =\lim_{n\to +\infty}\frac{1}{(n+1)\log\left(1+\frac{1}{n}\right)}=\color{red}{1}.$$

As an alternative, $$ 0\leq H_n-\log(n+1) = \sum_{k=1}^{n}\left(\frac{1}{k}-\log\left(1+\frac{1}{k}\right)\right)\leq\sum_{k=1}^{n}\frac{1}{2k^2}<\frac{\zeta(2)}{2}=\frac{\pi^2}{12} $$ is enough. It comes from a telescoping trick and the fact that $x-\log(1+x)\leq\frac{x^2}{2}$ over $[0,1]$.

$\endgroup$
  • $\begingroup$ That's really a useful theorem. I find it strange that I've never heard about it before... I wanted to try to understand the alternative, but I'm afraid I'm missing a bit too much in order to get it, but thanks anyway! If I get some spare time I have something new to think about ;) $\endgroup$ – Mr Tsjolder Apr 8 '16 at 19:07
0
$\begingroup$

It is

$H_n - 1 = \sum_{k=2}^{n} \frac{1}{k} \leq \sum_{k=2}^{n} \int_{k-1}^{k} \frac{1}{k} = \int_{1}^{n} \frac{1}{x} \mathrm{d}x = \ln (x)$

and

$H_n - \frac{1}{n} = \sum_{k=1}^{n-1} \frac{1}{k} \geq \sum_{k=1}^{n-1} \int_{k}^{k+1} \frac{1}{x} = \ln(x)$.

Hence $\ln (n) + \frac{1}{n} \leq H_n \leq \ln (n) + 1$.

Therefore $1 + \frac{1}{n \ln (n)} \leq \frac{H_n}{\ln (n)} \leq 1 + \frac{1}{\ln (n)}$.

You will get the desired result by $n \to \infty$.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.