Simple proof of showing the Harmonic number $H_n = \Theta (\log n)$ Consider the partial sum of the divergent Harmonic series $H_n = \sum\limits_{k = 1}^{n}\frac{1}{k}$. I recently saw a question which required finding out the asymptotic bounds of $H_n$. Now, I could not find any bound closer than $O(n)$. So I looked up the series and found this Wikipedia article which says that $H_n - \ln n$ approaches a constant (the Euler–Mascheroni constant). This clearly shows that $H_n = \Theta(\log n)$.
However, considering the question was in an beginners undergraduate algorithms course in CS, I was wondering if there is a simpler proof of this? Is there some clever proof requiring elementary mathematics to show $H_n = \Theta(\log n)$?
PS: This is not homework in the sense that it is not my homework, and the actual question does not ask for a proof, but rather asks a lot of functions to be arranged asymptotically.
 A: Just consider that $\frac{1}{x + 1} < \frac{1}{x}$, plot both and see that $H_n$ is the area under a "staircase" sandwiched between both curves (the image shows the lower bound for a similar situation). This gives rather tight bounds on $H_n$.

A: Let $u_n=H_n-\log n$. If we prove that the sequence $(u_n)_n$ is convergent (it's limit is the Euler constant $\gamma$) then we conclude that $H_n=\Theta(\log n)$.
We know that the sequence $(u_n)$ is convergent iff the series $\sum( u_{n}-u_{n-1})$ is convergent (the partial sums are just the terms of the sequence), so we calculate
$$u_{n}-u_{n-1}=\frac{1}{n}+\log(1-\frac{1}{n})=-\frac{1}{2n^2}+o(\frac{1}{n^2}),$$
and we show easily that the sum converges (Riemann series).
A: Here is an answer using limits, but no calculus.
Note that
$$
\begin{align}
H(2n)-H(n)
&=\sum_{k=1}^{2n}\frac1k-\sum_{k=1}^n\frac1k\\
&=\sum_{k=1}^n\frac1{2k-1}+\frac1{2k}-\frac1k\\
&=\sum_{k=1}^n\frac1{2k-1}-\frac1{2k}\\
&=\sum_{k=1}^{2n}(-1)^{k-1}\frac1k\tag{1}
\end{align}
$$
By the Alternating Series Test, $\displaystyle\sum_{k=1}^\infty(-1)^{k-1}\frac1k$ converges. Call the limit $\alpha$. Futhermore, the Alternating Series Test says that
$$
\alpha-\frac1{2n+1}\le H(2n)-H(n)\le\alpha\tag{2}
$$
Thus, summing $(2)$ yields
$$
(n-m)\alpha-\frac1{2^m}\le H(2^n)-H(2^m)\le(n-m)\alpha\tag{3}
$$
$(3)$ says precisely that
$$
H(2^n)\sim n\alpha\tag{4}
$$

Computation of $\alpha$
In this answer, It is shown that $\left(1+\frac1n\right)^n$ increases and $\left(1+\frac1n\right)^{n+1}$ decreases to $e$. Thus,
$$
\left(1+\frac1n\right)^n\le\left(1+\frac1{n+1}\right)^{n+1}\le\dots\le\left(1+\frac1{n+k}\right)^{n+k}\tag{5}
$$
and
$$
\left(1+\frac1n\right)^{n+1}\ge\left(1+\frac1{n+1}\right)^{n+2}\ge\dots\ge\left(1+\frac1{n+k}\right)^{n+k+1}\tag{6}
$$
Putting $(5)$ and $(6)$ together yields, for $0\le k\le n$,
$$
\left(1+\frac1{n+k}\right)^{\frac{n}{n+1}}\le\left(1+\frac1{n+k}\right)^{\frac{n}{n+k}\frac{n+k+1}{n+1}}\le\left(1+\frac1n\right)^\frac{n}{n+k}\le\left(1+\frac1{n+k}\right)\tag{7}
$$
Therefore,
$$
\begin{align}
e^\alpha
&=\lim_{n\to\infty}\left(1+\frac1n\right)^{n\left(\frac1{n+1}+\frac1{n+2}+\dots+\frac1{2n}\right)}\tag{8}
\end{align}
$$
and by $(7)$
$$
\begin{align}
\left(1+\frac1n\right)^{n\left(\frac1{n+1}+\frac1{n+2}+\dots+\frac1{2n}\right)}
&\le\left(1+\frac1{n+1}\right)\left(1+\frac1{n+2}\right)\dots\left(1+\frac1{2n}\right)\\
&=\frac{2n+1}{n+1}\tag{9}
\end{align}
$$
Using the other direction of $(7)$, we get
$$
\left(\frac{2n+1}{n+1}\right)^\frac{n}{n+1}
\le\left(1+\frac1n\right)^{n\left(\frac1{n+1}+\frac1{n+2}+\dots+\frac1{2n}\right)}\tag{10}
$$
By the Squeeze Theorem, $(8)$, $(9)$, and $(10)$ say
$$
e^\alpha=2\tag{11}
$$
which, by definition, means
$$
\alpha=\log(2)\tag{12}
$$
Since $H$ is monotonic, $(4)$, and $(12)$ say that
$$
H(n)=\Theta(\log(n))\tag{13}
$$
A: Apply the Abel partial summation formula
$\sum_{k \le x} a_k \varphi(k) = A(x)\varphi(x) - \int_1^x A(u)\varphi'(u) du$
where $A(x) = \sum_{k \le x} a_k$.
We have $\sum_{k \le x} 1.\frac1{k} = [x].\frac1{x} +\int_1^x[u]\frac1{u^2} du$
with $A(x) = \sum_{k \le x}1=[x]$ and $\varphi(u)=\frac1{u}$.
($\{{u}\}$ denote fractional part of u, and $[u]$ the entire part.)
As $u=[u]+\{u\}$, we have $\sum_{k \le x}\frac1k= \frac{[x]}{x}+ \int_1^x \frac1{u}du-\int_1^x \frac{\{u\}}{u^2}du = O(1) + \ln (x) - O(1/x).$
Hence $\sum_{k \le x} \frac1k=\ln(x) + O(1).$ 
Another method is to apply the Euler-MacLaurin formula
$\sum_{i=p}^{q}f\left(
i\right) =\int_p^q f(x)~{\rm d}x+\frac{f\left( p\right) +f\left( q\right) }{2}
+\sum_{j=1}^k\frac{b_{2j}}{(2j)!}\left(f^{(2j-1)}(q)-f^{(2j-1)}(p)\right)+R_k.$
The formula give with $f(u)=\frac1u$ immediately $\sum_{k \le x} \frac1k=\ln(x) + O(1).$ 
A: Here's my favorite "calculus-free" proof that $H_n = \Theta(\log n)$. This proof is essentially an extension of the calculus-free proof that the harmonic series diverges.
Start with the powers of 2, $n = 2^k$, and break up $H_{2^k}$ into $k$ groups, each one twice as large as the previous:
$$\begin{align*}
H_{2^k} = &\sum_{j = 1}^{2^k} \frac{1}{j} \\
= & 1 + \\ 
&\frac{1}{2} + \frac{1}{3} + \\ 
&\frac{1}{4}+\frac{1}{5} + \frac{1}{6} + \frac{1}{7}\\
& \cdots\\
& \frac{1}{2^{k-1}} + \frac{1}{2^{k-1} + 1} + \cdots + \frac{1}{2^k - 1}
\end{align*}$$
There's also one extra term, $\frac{1}{2^k}$.
We can bound each group above and below by a constant by bounding each term by the power of 2 above and below it.
\begin{array}{lll}
\frac{1}{2}& \leq 1 &\leq 1\\ 
\frac{1}{4}+\frac{1}{4}& \leq \frac{1}{2} + \frac{1}{3} &\leq \frac{1}{2} + \frac{1}{2}\\ 
\frac{1}{8} + \frac{1}{8} + \frac{1}{8} + \frac{1}{8}& \leq \frac{1}{4}+\frac{1}{5} + \frac{1}{6} + \frac{1}{7} & \leq \frac{1}{4} + \frac{1}{4} + \frac{1}{4} + \frac{1}{4}\\
& \cdots &\\
\frac{1}{2^k} + \frac{1}{2^k} + \cdots + \frac{1}{2^k} & \leq \frac{1}{2^{k-1}} + \frac{1}{2^{k-1} + 1} + \cdots + \frac{1}{2^k - 1} & \leq \frac{1}{2^{k-1}} + \frac{1}{2^{k-1}} + \cdots + \frac{1}{2^{k-1}}
\end{array}
Each of the left-hand sums is $\frac{1}{2}$. Each of the right-hand sums is 1. Together we have $\frac{1}{2}k +\frac{1}{2^k}\leq H_{2^k} \leq k + \frac{1}{2^k}$. Written in terms of $n$,
$$ \frac{1}{2} \log_2 n \leq H_n \leq \log_2n + 1$$
This is essentially the whole proof: it says when $n = 2^k$, $H_n = \Theta( \log n)$. For $n$ that aren't powers of 2, letting $n_-$ and $n_+$ be the surrounding powers of 2 of $n$, by monotonicity of $H_n$ and the observation that 
$$n/2 < n_- < n < n_+ < 2n$$
we have
$$\frac{1}{2}\log_2(n/2) < \frac{1}{2}\log_2 n_- < H_{n_-} < H_n < H_{n_+} < \log_2 n_+ +1< \log_2 (2n)+1$$
$$\frac{1}{2} \log_2n - \frac{1}{2} < H_n < \log_2 n + 2$$
And so $H_n = \Theta(\log n)$.
A: Improved after @robjohn
$$H_n=1+\frac{1}{2}+\frac{1}{3}+\frac{1}{4}+....+\frac{1}{n}.$$
If $[x]$ and $(x)$ are GIF and LIF respectively, then
for $x\ge 1$, we have
$$[x] \le  x \le (x) \implies \frac{1}{[x]} \ge \frac{1}{x} \ge \frac{1}{(x)} \implies \int_{1}^n\frac{dx}{[x]} > \int_1^n\frac{dx}{x} > \int_1^n \frac{dx}{(x)}, n>1. $$
$$\implies H_{n-1} > \log n > H_n-1\implies \log n+1/n < H_n 
< 1+\log n.$$ Equalities hold when $n=1$.
