Prove that $ 1 + \frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{n} = \mathcal{O}(\log(n)) $. Prove that $ 1 + \dfrac{1}{2} + \dfrac{1}{3} + \cdots + \dfrac{1}{n} = \mathcal{O}(\log(n)) $, with induction.
I get the intuition behind this question. Clearly, the given function isn’t even growing at a linear rate, but what is the ‘proper’ proofy way to say that $ \displaystyle \sum_{k=1}^{n} \frac{1}{k} \leq \mathcal{O}(\log(n)) $? I was unable to find any useful identities to use for such a summation.

Using the inequality $1+x\le e^x$, we can derive
$$
\log\left(\frac{n+1}{n}\right)=\log\left(1+\frac1n\right)\le\frac1n\le-\log\left(1-\frac1n\right)=\log\left(\frac{n}{n-1}\right)\tag{1}
$$
Summing $(1)$ yields
$$
\log(n+1)\le\sum_{k=1}^{n}\frac1k=1+\sum_{k=2}^{n}\frac1k\le1+\log(n)\tag{2}
$$
That is, for all $n\ge1$
$$
\log(n+1)\le\sum_{k=1}^{n}\frac1k\le1+\log(n)\tag{3}
$$

Sums can easily be made into inductions. We will prove $(3)$ by induction using $(1)$.
For $n=1$, $(3)$ holds since $\log(2)\le1\le1$.
Suppose we have $(3)$ for $n-1$:
$$
\log(n)\le\sum_{k=1}^{n-1}\frac1k\le1+\log(n-1)\tag{4}
$$
Inequality $(1)$ says that
$$
\log\left(\frac{n+1}{n}\right)\le\frac1n\le\log\left(\frac{n}{n-1}\right)\tag{5}
$$
Adding $(4)$ to $(5)$ yields
$$
\log(n+1)\le\sum_{k=1}^{n}\frac1k\le1+\log(n)\tag{6}
$$
which is $(3)$ for $n$. This finishes the induction.
