2
$\begingroup$

I wish to verify that Harmonic numbers $H_n = \sum_{k=1}^{n} \frac{1}{k}$ are $\Theta(\log n)$.

One idea I have is to approximate the sum with an integral:

$$\int_{1}^{n} \frac{1}{k} ~dk = \log(n) - \log(1) = \log(n)$$

But I don't know if this is valid and I want a more direct proof.

In other words I want to show that:

$$\sum_{k=1}^{n} \frac{1}{k} \leq c \log n$$

and

$$\sum_{k=1}^{n} \frac{1}{k} \geq d \log n$$

For some $n \geq n_0$ and positive reals $c,d$. Is there an intuitive way to do this that doesn't rely on weird calculus tricks? I see derivations in the post here:

Simple proof of showing the Harmonic number $H_n = \Theta (\log n)$

but none of these seem intuitive to me (they rely on higher calculus and series tests and Riemann sums).

$\endgroup$
  • 2
    $\begingroup$ Of course the integral comparison is valid, once you fill in the details. Did you have a look at vonbrand's answer in the post you linked to? math.stackexchange.com/a/306674/30402 $\endgroup$ – Erick Wong Feb 11 '16 at 20:11
  • $\begingroup$ @ErickWong Yes, but I don't understand how it's a proof $\endgroup$ – Nakano Feb 11 '16 at 20:16
  • $\begingroup$ I don't understand how it's not a proof. It's a straightforward application of the fact that if $f(x) \ge g(x)$ on some interval $[a,b]$ then $\int_a^b f(x) dx \ge \int_a^b g(x) dx$. There are details that need to be filled in but you asked whether it was valid, not whether it was fully worked out in detail. $\endgroup$ – Erick Wong Feb 11 '16 at 20:25
  • $\begingroup$ @ErickWong I'll phrase another way: Given that $\int_a^b f(x) dx \ge \int_a^b g(x) dx$, so what? How does this show that $H_n$ is $\log n$? $\endgroup$ – Nakano Feb 11 '16 at 20:29
  • $\begingroup$ @Nakano This is the first property used in the answer I gave. $f(n) \geq f(x) \geq f(n+1)$ for any $x\in[n,n+1]$ implies $1\cdot f(n) = \int_n^{n+1} f(n)dx\geq \int_n^{n+1} f(x) dx \geq \int_n^{n+1} f(n+1)dx = 1\cdot f(n+1)$.) $\endgroup$ – Clement C. Feb 11 '16 at 20:33
3
$\begingroup$

\begin{align} & \frac 1 2 \le \int_1^2 \frac{dx} x \le 1 \\[8pt] & \frac 1 3 \le \int_2^3 \frac{dx} x \le \frac 1 2 \\[8pt] & \frac 1 4 \le \int_3^4 \frac{dx} x \le \frac 1 3 \\[8pt] & \qquad \qquad \vdots \\[10pt] \text{Hence } & \frac 1 2 + \frac 1 3 + \frac 1 4 + \cdots + \frac 1 {n+1} \le \int_1^{n+1} \frac{dx} x \le 1 + \frac 1 2 + \frac 1 3 + \cdots + \frac 1 n. \end{align} And finally, $$ 1 + \int_1^n \frac{dx} x \ge 1+ \frac 1 2 + \frac 1 3 + \cdots + \frac 1 n \ge \int_1^{n+1} \frac {dx} x, $$ i.e. $$ 1 + \log n \ge H_n \ge \log(n+1). $$

$\endgroup$
4
$\begingroup$

You can show that as $n \to \infty$ we have the asymptotic behavior

$$H_n \sim \log n,$$

directly as a limit of a sequence.

By the Stolz-Cesaro theorem (L'Hospital's rule for sequences)

$$\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(1 + 1/n)} \\ = \lim_{n \to \infty}\frac{1}{\log(1 + 1/n)^{n+1}} \\ = \frac{1}{\log e} \\ = 1.$$

$\endgroup$
  • 1
    $\begingroup$ I like this answer, but not sure why Stolz–Cesàro would not fall under "higher calculus" (or fancy theorems). The proof is simple and short, but the tool (theorem) it uses is not. +1 anyway. $\endgroup$ – Clement C. Feb 11 '16 at 20:43
2
$\begingroup$

Here's a direct approach that avoids calculus to obtain just the weak result of $\Theta(\log n)$ rather than the more precise asymptotic $(1+o(1)) \log n$.

First consider the special case that $n$ is of the form $2^k - 1$, and divide $H_n$ into dyadic blocks:

$$H_n = \big(1\big) + \big(\frac12 + \frac13\big) + \big(\frac14 + \cdots + \frac17\big) + \cdots + \big(\frac{1}{2^{k-1}} + \cdots + \frac1{2^k-1}\big),$$ where there are $k$ blocks and each block has twice the number of terms as the previous one. Now the following two inequalities are obvious by term-by-term comparison:

$$H_n \le \big(1\big) + \big(\frac12 + \frac12\big) + \big(\frac14 + \cdots + \frac14\big) + \cdots + \big(\frac{1}{2^{k-1}} + \cdots + \frac1{2^{k-1}}\big) = 1 + 1 + \cdots + 1 = k,$$

$$H_n \ge \big(\frac12\big) + \big(\frac14 + \frac14\big) + \big(\frac18 + \cdots + \frac18\big) + \cdots + \big(\frac{1}{2^k} + \cdots + \frac1{2^k}\big) = \frac12 + \frac12 + \cdots + \frac12 = \frac k2.$$

Therefore, for these special values of $n$, $\frac k2 \le H_n \le k$. Since $k = \log(n+1)/\log 2$, this is clearly $\Theta(\log n)$. This gives the intuition (which your question explicitly asks for), now to fill in the details for arbitrary $n$ you just need to use the fact that $H_n$ is monotonically increasing and that you can always find consecutive powers of $2$ that bracket $n$.

$\endgroup$
1
$\begingroup$

Your idea of approximation with an integral works. This is a classical exercise: let $f\colon x > 0\mapsto \frac{1}{x}$ (works with any monotone function $f$ such that $\lim_{x\to \infty}f(x) = 0$):

Fix any $n \geq 1$. For all $n \leq x \leq n+1$, $$ f(n+1) \leq f(x) \leq f(n) $$ so that, integrating, $$ f(n+1) = \int_n^{n+1} f(n+1) dx \leq\int_n^{n+1} f(x) dx \leq \int_n^{n+1} f(n) dx = f(n) $$ which holds for any integer $n\geq 1$. Now, sum this inequality for $n$ ranging from $1$ to $N-1$: $$ \sum_{n=1}^{N-1} f(n+1) \leq \sum_{n=1}^{N-1} \int_n^{n+1} f(x) dx \leq \sum_{n=1}^{N-1} f(n) $$ that is exactly (using for the middle term that $\int_a^b f + \int_b^c f = \int_a^c f$): $$ \sum_{n=2}^{N} f(n) \leq \int_1^{N} f(x) dx \leq \sum_{n=1}^{N-1} f(n). $$ Rearranging, $$ \int_1^{N} f(x) dx + f(N) \leq \sum_{n=1}^{N} f(n) \leq f(2) + \int_1^{N} f(x) dx $$ which gives, in our case, $$ \ln N + \frac{1}{N} \leq \sum_{n=1}^{N} f(n) \leq \frac{1}{2} + \ln N $$

$\endgroup$
  • $\begingroup$ What is "$f\colon x > 0\mapsto \frac{1}{x}$"? $\endgroup$ – Nakano Feb 11 '16 at 20:16
  • $\begingroup$ OP asked for "intutive proof", "not relying on higher calculus and series tests and Riemann sums". $\endgroup$ – vrugtehagel Feb 11 '16 at 20:16
  • $\begingroup$ @Nakano Just notation for "a function $f$ defined on $(0,\infty)$, by $f(x) = \frac{1}{x}$." $\endgroup$ – Clement C. Feb 11 '16 at 20:19
  • $\begingroup$ Also I'm sure this approach is valid but I find all the chained inequalities hard to follow -- I'm not sure what you're doing or why you're doing it, and then I get totally lost when you're summing integrals. To me that is not intuitive. I don't know why you choose bound $n+1$ or where $N-1$ comes from, either. $\endgroup$ – Nakano Feb 11 '16 at 20:19
  • 1
    $\begingroup$ @vrugtehagel If that is the case, then I would find the question quite... puzzling. The OP did state "One idea I have is to approximate the sum with an integral"... which presupposes that integration (and basic properties of integrals, such as the two used here) are not out of the picture. $\endgroup$ – Clement C. Feb 11 '16 at 20:29

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.