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.

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)$.
