How to show that the harmonic function $H(n) = 1 + \frac{1}{2} + · · · + \frac{1}{n} = O(\log n)$ using simple inequalities on fractions?

Question

How can I prove that $H(n) = 1 + \frac{1}{2} + · · · + \frac{1}{n} = O(\log n)$ using simple inequalities on fractions?

Answer 1

We have $$ 1 + \cdots + \frac1n \leq 1 + \frac 12 + \frac 12 + \frac14 + \frac14 + \frac14 + \frac14 + \cdots + \frac{1}{2^{k}} $$ where what we do is substitute the denominator of any fraction $\frac 1i$ where $i$ is not a power of $2$ with the largest power of $2$ below $i$ (there are still $n$ terms, so specifically, $2^k \leq n < 2^{k+1}$)

The sum of all fractions with a given power of $2$ in the above sequence is $1$ (apart from possibly the last, which might be smaller, depending on what $n$ is). This means that the right-hand sum is below or equal to $k + 1$.

But what is $k$? To be exact, it's $\lfloor \log_2 n\rfloor + 1 \leq \log_2 n + 2$. Thus we have that $H(n) \leq \log_2 n + 3$. Therefore it's bounded by $2\log_2 n$ for any $n \geq 8$. If you would rather have it in natural logrithms, then $\log_2 n = \frac{\ln n}{\ln 2}$, so $H(n) \leq \frac{2}{\ln 2}\ln n$ for $n \geq 8$.

Answer 2

If you know that $\log x = \int_1^x \frac{1}{t} dt$, either by definition or by $\frac{d}{dt}\log(t) = \frac1t$ and the fundamental theorem of calculus, then it is as simple as noting that $H(n)-\log(n)$ is the area of a certain region in the plane consisting of connected pieces that can be translated horizontally to stack within a unit square.

So $|H(n)-\log(n)|\le 1 $ always, and in fact $H(n)$ is $\Theta(\log n)$.

---

More formally: $H(n) = \int_1^{n+1} \frac{1}{\lfloor t \rfloor} dt$. Then if we exclude the area below $1/t$ for $1<t<n$ and estimate $$ \int_a^{a+1} \left( \frac1{\lfloor t\rfloor} - \frac1t \right) dt < \int_a^{a+1} \left( \frac1a - \frac1{a+1} \right) dt = \frac1a-\frac1{a+1} $$ and the contributions of these for each unit interval of $t$ now telescope.

Answer 3

Hint. Prove by induction that $$1+\frac{n}{2}\leq H_{2^n}\leq 1+n$$ by using the fact that $$\frac{1}{2}=\frac{2^n}{2^n+2^n}\leq H_{2^{n+1}}-H_{2^n}=\frac{1}{2^n+1}+\frac{1}{2^n+2}+\cdots +\frac{1}{2^{n}+2^n}\leq \frac{2^n}{2^n+1}<1.$$

Answer 4

Well since everyone is throwing their hat in the ring; here is mine.

Show the sequence $$\sum \frac{1}{n}-\ln\left(1+\frac{1}{n}\right)$$ converges by comparison with $\frac{1}{n(n+1)}$.

The partial sum is $1+\frac{1}{2}+\cdots \frac{1}{n}-\ln (n+1)$

Answer 5

For any $n\geq 2$ we have that $$ \frac{1}{n}<\frac{1}{n}+\frac{1}{3n^3}+\frac{1}{5n^5}+\ldots=\text{arctanh}\frac{1}{n} = \frac{1}{2}\log\frac{n+1}{n-1}\tag{1}$$ hence we may exploit a telescopic sum:

$$\begin{eqnarray*} H_n = 1+\sum_{k=2}^{n}\frac{1}{k} &<& 1+\frac{1}{2}\sum_{k=2}^{n}\left(\log(k+1)-\log(k-1)\right)\\&=&1+\frac{1}{2}\left(\log(n+1)+\log(n)-\log(2)\right)\\&<&\left(1-\frac{\log 2}{2}\right)+\log(n+1).\tag{2} \end{eqnarray*}$$ The inequality $$ \frac{1}{n}<\log\left(n+\frac{1}{2}\right)-\log\left(n-\frac{1}{2}\right)\tag{3}$$ leads to the sharper (and simpler) bound $$ \boxed{H_n < \color{red}{ \log(2n+1)}} \tag{4} $$ through the same technique.

Answer 6

Well, I would also like to post an answer with a formulation similar to the one I accepted above.

$$1 + \frac{1}{2} + \frac{1}{3} + ... +\frac{1}{n} = \sum_{r=0}^{\lfloor \log n \rfloor} \sum_{j=0}^{2^{r} - 1} \frac{1}{2^{r} + j } ≤ \sum_{r=0}^{\lfloor \log n \rfloor} \sum_{j=0}^{2^{r} - 1} \frac{1}{2^{r} } = \sum_{r=0}^{\lfloor \log n \rfloor} 1 ≤ \log n $$ So, H(n) = O(log n)