# Proving that the Harmonic Series is divergent

1. Sep 5, 2013

### Seydlitz

1. The problem statement, all variables and given/known data
Prove harmonic series is divergent by comparing it with this series.

$\frac{1}{1}+\frac{1}{2}+(\frac{1}{4}+\frac{1}{4})+(...)$

3. The attempt at a solution

Clearly every term in harmonic series is equal or larger than the term in the second series $n \geq 1$, hence like the second series the harmonic series must be divergent. The second series denominator has the form $2^k$. For any integer $k$, $\frac{1}{n} \geq \frac{1}{2^k}$

Is this proof good enough? If not how do I formalize the proof more? What needs to be shown in this case?

2. Sep 5, 2013

### clamtrox

You should show that every term in harmonic series is larger or equal than the corresponding term in your comparison series. This should be clear from the way you construct the series. Then you should show that the comparison series diverges.

3. Sep 5, 2013

### Curious3141

This statement has no meaning at all. What is $n$ here? Can I choose $n=100$ and $k = 3$ and expect that statement to hold?

What you need to do is write out a couple more "bracket enclosed" sums and make the observation that within the brackets, each term in the harmonic series is greater than or equal to the corresponding term in the other series. Since the other series is just 1 + half + half +... ad infinitum, it is clearly divergent, and therefore, so is the harmonic series.

Writing out a very rigorous proof is tedious, and probably quite unnecessary here. But I would be very clear with my bracketing and use arrows to emphasise the correspondence between terms to show the relationship clearly.

4. Sep 5, 2013

### Seydlitz

I seem to have a little bit of difficulty in expressing formally, that the term of the harmonic series is always greater or equal to the term of the secondary series. I want to show that the term on the secondary series is based from geometric series and that you can choose this to set an upper bound to the harmonic term. Say for $n=4$, we can choose $k=2$, therefore the terms in harmonic series is always greater than or equal to the secondary series. How would you express this symbolically?

$$\frac{1}{n} \geq \frac{1}{2^{n-1}}$$

I am aware of the sum that involves proof but the book specifically mentions that we need to use comparison test with the given series to prove the divergence of harmonic series.

Edit: I realize why don't we just compare the harmonic series with geometric series with $r=1/2$, the term in harmonic series are always greater or equal to the term in geometric series?

Last edited: Sep 5, 2013
5. Sep 5, 2013

### Curious3141

Because a geometric series is convergent. How does comparing the harmonic series with that help to prove divergence of the harmonic series?

What you're basically trying to say is that, for every $k \geq 1$, every term in the bracketed subsequence $\displaystyle \frac{1}{2^k + 1}, \frac{1}{2^k + 2}, \frac{1}{2^k + 3},...,\frac{1}{2^{k+1}}$ (where the denominators are consecutive natural numbers) is greater than or equal to $\displaystyle \frac{1}{2^{k+1}}$.

How would you prove that rigorously? It isn't difficult. For starters, figure out how many terms there are in a bracket that ends with the last term $\displaystyle \frac{1}{2^{k+1}}$.

6. Sep 5, 2013

### Seydlitz

D'oh my bad. I'll do what you ask of me for a while and I'll report back the result a bit later. Thanks!

Edit:
Nvm.

Last edited: Sep 5, 2013
7. Sep 5, 2013

### Seydlitz

The terms are indeed greater than or equal to $\frac{1}{2^{k+1}}$

$k=0$ (1 terms in bracket)
$$\frac{1}{1},\frac{1}{2} \geq \frac{1}{2}$$
$k=1$ (2 terms in bracket)
$$\frac{1}{3},\frac{1}{4} \geq \frac{1}{4}$$
$k=2$ (4 terms in bracket)
$$\frac{1}{5}, \frac{1}{6}, \frac{1}{7}, \frac{1}{8} \geq \frac{1}{8}$$

So the number of terms in the bracket that ends with $\frac{1}{2^{k+1}}$ in the secondary series is $2^{k-1}$. How can I proceed further then?

8. Sep 5, 2013

### Curious3141

Ignore the first 1 and $\frac{1}{2}$ terms. You only start comparing the series from the respective pairings $(\frac{1}{3} + \frac{1}{4})$ (Harmonic) and $(\frac{1}{4} + \frac{1}{4})$ (the other series).

So for k = 1, there are two terms (2^1).

For k = 2 (subsequence ending with 1/8), there are four terms (2^2)

For k = 3 (subsequence ending with 1/16), there are eight terms (2^3).

Isn't the no. of terms $2^k$?

For the bracketed subsequences in the harmonic series, you start with a reciprocal of one more than a power of 2, i.e. $\frac{1}{2^k + 1}$. There are $2^k$ terms with the denominator going up consecutively. Verify that this will end with $\frac{1}{2^{k+1}}$, which is the reciprocal of the next higher power of 2.

Since the denominator is strictly increasing for the harmonic subsequence, the terms are getting steadily smaller. So all you need to do is verify that the last term in the subsequences are equal between the two series, and you're done. Because the implication is that every term in the harmonic sequence from $\frac{1}{2^k + 1}$ to $\frac{1}{2^{k+1}}$ is greater than equal to $\frac{1}{2^{k+1}}$.

All that's left to do is to show that the bracketed subsequences in the other series always add up to half. There are $2^k$ terms, each of which is $\frac{1}{2^{k+1}}$, just multiply.

9. Sep 6, 2013

### Seydlitz

Ok it's $2^k$ if we start with the pairing.

If $n=2^{k+1}$ the term of the harmonic series $\frac{1}{n}$ will be always equal to the term in the secondary series pair. There will be always $k$ such that the lower term $n<2^{k+1}$ will be always greater than the secondary series. We can therefore conclude that the term of harmonic series are always greater or equal to the secondary.

The multiplication will result in $\frac{1}{2}$. This fact can be used to show that harmonic series must be divergent because the terms of harmonic series are always greater or equal to divergent series.

The proof seems completed now but I'd very appreciate it if you could show your own finished version once you're satisfied with mine. I can assure you that I'm not trying to cheat as this is not homework but a self-study question. I just hope I can create my own from scratch with your hints.

10. Sep 6, 2013

### Curious3141

I wouldn't even introduce $n$ here, it's needlessly confusing.

You asked for how I would write it out. Here's how:

The harmonic series is defined by $H = \frac{1}{1} + \frac{1}{2} + \frac{1}{3} + ...$.

Let us group the terms beginning with $\frac{1}{3}$ into bracketed subsequences without changing their order. A bracketed subsequence $B_k$ is defined as follows: $\forall k \geq 1, B_k = (\frac{1}{2^k + 1}, \frac{1}{2^k + 2}, ..., \frac{1}{2^k + 2^k})$. Hence every $B_k$ contains exactly $2^k$ terms.

Now we establish that $B_k$ and $B_{k+1}$ do not overlap (i.e. the subsequences have no terms in common) and also that they occur consecutively within $H$. To do this, we observe that the final term in $B_k = \frac{1}{2^k + 2^k} = \frac{1}{2.2^k} = \frac{1}{2^{k+1}}$. Since $B_{k+1}$ begins with $\frac{1}{2^{k+1} + 1}$, there is no overlap. It is also clear that since $2^{k+1}$ and $2^{k+1} + 1$ are consecutive natural numbers, $B_k$ and $B_{k+1}$ occur consecutively within the harmonic series $H$. By induction, it is trivial to observe that since this holds for some $k$ and also clearly for $B_1$, it holds for all $k \geq 1$.

We now construct another series comprised solely of reciprocals of powers of 2 as follows: $S = 1 + \frac{1}{2} + \frac{1}{4} + \frac{1}{4} + \frac{1}{8} + \frac{1}{8} + \frac{1}{8} + \frac{1}{8} + ...$. It should be noted that $\forall k \geq 1$, the term $\frac{1}{2^{k+1}}$ occurs exactly $2^k$ times, and is then followed by $\frac{1}{2^{k+2}}$.

We can therefore group this sequence into bracketed subsequences as follows: $\forall k \geq 1$, every group $B'_k$ consists of $2^k$ instances of the term $\frac{1}{2^{k+1}}$. It is trivial to note that there is no overlap and that the subsequences are consecutive within $S$.

We can now compare the subsequences $B_k$ and $B'_k$. The final terms in these subsequences are equal. Furthermore, the terms in $B_k$ are strictly decreasing, whereas every term in $B'_k$ is identical. Hence, $\forall k \geq 1$, every term in $B_k$ is greater than or equal to every term in $B'_k$.

Since the subsequences are consecutive and non-overlapping, it is clear that every term in $H$ is greater than or equal to every corresponding term in $S$. It only remains to prove that $S$ diverges.

In $S$, every subsequence $B'_k$ sums to $(2^k).(\frac{1}{2^{k+1}}) = \frac{1}{2}$. Hence $S = 1 + \frac{1}{2} + \frac{1}{2} + \frac{1}{2} + ...$, which is clearly divergent.

Therefore, by the comparison test, $H$ also diverges. (QED).

You'll note that this proof is far more verbose than is probably needed for your problem, although it is rigorous. I also wrote it from the perspective of constructing a series $S$ for comparison, whereas in your question, $S$ was already defined and you were instructed on how to compare it with the harmonic series.

Last edited: Sep 6, 2013
11. Sep 6, 2013

### Seydlitz

Ah so that's how you can group the term rigorously. I really didn't have the idea to formulate the groupings clearly. Yours are very clear, and I have to say clearer than any other proof out there.

Thank you very much for your help, one always learns new thing everyday. The harmonic series has been quite a mystery for me sometimes.

Do you happen to know good books to practice writing proof? There seems to be many techniques depending on which area of math we are studying.

12. Sep 6, 2013

### Curious3141

Not a personal recommendation, since I haven't read them myself, but this thread seems to be a good place to start. Especially this post (under "Proof and Foundation"), although there are other posts with other books that look promising. Hopefully, that'll get you off to a good start, good luck!

Off topic, but I thought I should mention this apropos of your avatar - I've just started watching Star Trek's The Original Series Season 1 recently. I'm up to Episode 10 ("Dagger of the Mind") currently.

Last edited: Sep 6, 2013
13. Aug 26, 2017

### EternusVia

Hello everyone,

I too had to solve this problem, and I think I found a nice way to write the solution. I'd like to share it here.
We can regroup the harmonic series as follows:
$$\sum_{n=1}^{\infty} \frac{1}{n} = 1+\frac{1}{2}+\left(\frac{1}{3}+\frac{1}{4}\right)+\left(\frac{1}{5}+\frac{1}{6}+\frac{1}{7}+\frac{1}{8}\right)+\left(\frac{1}{9}+\frac{1}{10}+\cdots\right) + \cdots$$
It takes some thinkin', but this can be expressed as
$$\sum_{n=1}^{\infty} \frac{1}{n} = \frac{3}{2} + \sum_{n=1}^{\infty} \left( \sum_{k=2^n+1}^{2^{n+1}} \frac{1}{k} \right)$$
Now we compare the expression on the right to the series
$$\sum_{n=1}^{\infty}a_n = \frac{3}{2} + \frac{1}{2} + \frac{1}{2} + \cdots$$
Clearly, $\frac{3}{2} \geq \frac{3}{2}$. Let $n \in \mathbb{N}$. Then
$$\sum_{k=2^n+1}^{2^{n+1}} \frac{1}{k} = \frac{1}{2^n+1} + \frac{1}{2^n+2} + \cdots + \frac{1}{2^{n+1}} \geq \frac{1}{2^{n+1}}+\frac{1}{2^{n+1}} + \cdots + \frac{1}{2^{n+1}} = \frac{2^n}{2^{n+1}}=\frac{1}{2}$$
Thus, by the comparison test, the harmonic series diverges!

Last edited: Aug 26, 2017
14. Aug 26, 2017

### Ray Vickson

No, you need to include more details (just to make sure you are not fooling yourself).

However, if you can avoid such a series-comparison method altogether, there are much easier ways. My favorite is to note that
$$\frac{1}{n} > \int_n^{n+1} \frac{1}{x} \, dx \;\; \text{(look at the graph!)}$$
so $\sum_{n=1}^N 1/n > \sum_{n=1}^N \int_{n}^{n+1} dx/x = \int_1^{N+1} dx / x = \ln(N+1)$, and this last quantity $\to +\infty$ as $N \to \infty$.

This method also gives a good way to get asymptotic expressions for $\sum_{n=1}^N 1/n$ for large $N$. We already have a lower bound, and we can get an upper bound from
$$\int_{n-1}^n \frac{1}{x} \, dx > \frac{1}{n},$$
so $\int_1^N dx/x = \ln (N) > \sum_{n=2}^N 1/n.$ We can even get fancier bounds by doing a bit more work along similar lines, getting better upper and lower bounds on $1/n$.

Last edited: Aug 26, 2017