<s>[INST] 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.
 [/INST] I'm expanding the answer by xan:
Define $H_n=\displaystyle\sum_{1\le k\le n} {1\over k}$, let's prove by induction that $H_{2^n}\le n+1$. This is true for $n=0$ since $H_{2^0}=H_1=1\le 1$.
Now suppose $H_{2^n}\le n+1$. We have:
$$\begin{align}
H_{2^{n+1}} &= \sum_{1\le k\le 2^{n+1}} {1\over k} \\
H_{2^{n+1}} &= \sum_{1\le k\le 2^n} {1\over k} + \sum_{2^n+1\le k\le 2^{n+1}} {1\over k} \\
H_{2^{n+1}} &= H_{2^n} + \sum_{2^n+1\le k\le 2^{n+1}} {1\over k} \\
H_{2^{n+1}} &\le H_{2^n} + \sum_{2^n+1\le k\le 2^{n+1}} {1\over 2^n} \\
H_{2^{n+1}} &\le H_{2^n} + (2^n-1){1\over 2^n} \\
H_{2^{n+1}} &\le H_{2^n} + (1-{1\over 2^n}) \\
H_{2^{n+1}} &\le H_{2^n} + 1 \\
H_{2^{n+1}} &\le (n+1) + 1 \\
H_{2^{n+1}} &\le n+2 \\
\end{align}
$$
Now let's make $m=2^n$, then $n=\lg m$, and:
$$H_{2^n}=H_m\le\lg m+1=\mathcal{O}(\log m)$$
</s>