How to show that the harmonic function $H(n) = 1 + \frac{1}{2} + · · · + \frac{1}{n} = O(\log n)$ using simple inequalities on fractions? How can I prove that $H(n) = 1 + \frac{1}{2} + · · · + \frac{1}{n} = O(\log n)$ using simple inequalities on fractions?
 A: 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$.
A: 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.
A: 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)
A: 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.$$
A: 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)$
A: 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.
