Showing that Harmonic numbers are $\Theta(\log n)$, intuitively 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). 
 A: 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.$$
A: \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).
$$
A: 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$.
A: 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
$$
