Example: H_N, the Harmonic Series, Diverges

Divergence of the harmonic series

The harmonic series, $1+\frac{1}{2}+\frac{1}{3}+\dots+\frac{1}{n}+\dots$, or

$$\sum_{n=1}^{\infty}\frac{1}{n}$$

in sigma notation, is an interesting series. Its terms are fractions that are strictly decreasing and approaching 0. Can we bound this?

It turns out that this series diverges. There are many ways to show this, including the integral test (the antiderivative of $\frac{1}{x}$ is $\ln x$, which grows without bound as $x \to \infty$. The simplest way, however, is by direct comparison.

Let's start our new series. In direct comparison, we want to bound the harmonic series from the bottom. In our harmonic series, let's look at 1. To keep it simple, let's just bound it by 1. Let's look at $\frac{1}{2}$. We can either bound it by $\frac{1}{2}$ or look further.

If we look further, then we pair $\frac{1}{2}$ with $\frac{1}{3}$. This sums to $\frac{5}{6}$, and there doesn't seem to be an easy divergent series that starts out $1,\frac{5}{6},\dots$. If we look further, that would over-complicate things. We choose $\frac{1}{2}$ as the next term in our new series. Let's look at $\frac{1}{3}$.

If we set the next term in our new series to be $\frac{1}{3}$, then it would seem counter-productive. Let's pair $\frac{1}{3}$ with $\frac{1}{4}$ to get $\frac{7}{12}$, so we're looking for a term at most $\frac{7}{12}$. Recall that the series starts $1,\frac{1}{2},\dots$. Let's try to find a simple next-term.

Among $1,\frac{1}{2},\frac{7}{12}$, fractions we just encountered, 1 is not at most $\frac{7}{12}$, and $\frac{7}{12}$ itself is too complicated. Luckily, $\frac{1}{2}$ is less than $\frac{7}{12}$, so we choose that to be our next term. $1+\frac{1}{2}+\frac{1}{2}+\frac{1}{2}+\dots$ is desired; great!

If we just start combining terms in the harmonic series until they sum to at least $\frac{1}{2}$, then we see that it's going to become complicated. When deciding our next combination, we know we're going to start with $\frac{1}{5}$, but we have to decide what to end at. Let's investigate $\frac{1}{3}+\frac{1}{4}\ge\frac{1}{2}$. We decided to end at $\frac{1}{4}$, and it has to do with $\frac{1}{2}$ somehow. Let's move them to the same side. $\frac{1}{3}\ge\frac{1}{2}-\frac{1}{4}=\frac{1}{4}$. Hey, it's $\frac{1}{4}$ again, the number we ended at!

Now assume our next combination is $\frac{1}{5}+\frac{1}{6}+\dots+\frac{1}{n}$. Clearly, $\frac{1}{5}\ge\frac{1}{n}$, $\frac{1}{6}\ge\frac{1}{n}$, $\dots$, $\frac{1}{n}\ge\frac{1}{n}$. When we sum all of this, we get $\frac{1}{5}+\frac{1}{6}+\dots+\frac{1}{n}\ge\frac{n-4}{n}$. We want the right hand side equal to $\frac{1}{2}$, and this only happens in one case.

$n=8$. So we stop at 2, 4, 8, and so on---powers of two. Does our result hold in general? Continuing on, we see that if $2^n+1\le k\le 2^{n+1}$, then $\frac{1}{k}\ge\frac{1}{2^{n+1}}$, and summing this over the given interval gives us what we desire---that we can bound the set of terms of our harmonic sequence by $\frac{1}{2}$. Thus, by comparison, the harmonic sequence diverges. $\blacksquare$