I'm trying to understand the following proof for the divergence of the harmonic series:
The parts which I can't seem to understand are: $$1. \sum_{i=0}^{n-1} \sum_{r=2^i+1}^{2^{i+1}} \frac{1}{r} > \sum_{i=0}^{n-1} \sum_{r=2^i+1}^{2^{i+1}} \frac{1}{2^{i+1}}$$ $$2. \sum_{i=0}^{n-1} \sum_{r=2^i+1}^{2^{i+1}} \frac{1}{2^{i+1}} = \sum_{i=0}^{n-1} (2^{i+1} - 2^i)\frac{1}{2^{i+1}}$$
I think understanding 2. follows from understanding 1. but I'm not entirely sure. Anyway for 1. I couldn't understand if the series on the RHS of the equality was $(\frac{1}{2^3})+(\frac{1}{2^3} + \frac{1}{2^4})+(\frac{1}{2^5} + \frac{1}{2^6}+\frac{1}{2^7}+\frac{1}{2^8})+...$ or $(\frac{1}{2^1})+(\frac{1}{2^2} + \frac{1}{2^3})+(\frac{1}{2^4} + \frac{1}{2^5}+\frac{1}{2^6}+\frac{1}{2^7})+...$ . And for part I simply could not understand 2. (probably because I didn't understand 1.). So I'm wondering what the series on the RHS of 1. actually is and how it equals $\sum_{i=0}^{n-1} (2^{i+1} - 2^i)\frac{1}{2^{i+1}}$ .
$\endgroup$ 22 Answers
$\begingroup$It's useful to look just at the difference between each term in the sequence $\{S_{2^n}\}$, i.e., $$S_{2^{n+1}} - S_{2^n} = \sum_{k = 2^n+1}^{2^{n+1}} \frac{1}{k} \geq \sum_{k = 2^n+1}^{2^{n+1}} \frac{1}{2^{n+1}} = \frac{1}{2^{n+1}} \sum_{k = 2^n+1}^{2^{n+1}} 1 = \frac{2^n}{2^{n+1}} = \frac{1}{2}.$$
So $S_{2^{n+1}}\geq S_{2^n} + \frac{1}{2} $ for all $n$. If the partial sums increase by at least $\frac{1}{2}$ each time, the series must diverge to infinity.
$\endgroup$ $\begingroup$Look at how the terms are grouped early on:
$$ \sum_{k=1}^{\infty} \frac{1}{k} = 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) + \cdots $$ Note that $$ 1 = \sum_{r=0}^{0} 2^{0} \qquad\text{and}\qquad \frac{1}{2} = \sum_{r=1}^{1} 2^{-1} = \sum_{r=2^0}^{2^1-1} 2^{-1} $$ In the next group, note that $3 < 4 = 2^2$, from which it follows that $\frac{1}{3} > 2^{-2}$. The second term is $\frac{1}{4}$, which is exactly $2^{-2}$, and so we have $$ \frac{1}{3} + \frac{1}{4} > 2^{-2} + 2^{-2} = \sum_{r=2}^{3} 2^{-2} = \sum_{r=2^1}^{2^2-1} 2^{-2}. $$ In the next group, note that $$ \frac{1}{5} > \frac{1}{6} > \frac{1}{7} > \frac{1}{8} = 2^{-3}. $$ That is, every element of this group is larger than $2^{-3}$. From this, it follows that $$ \frac{1}{5} + \frac{1}{6} + \frac{1}{7} + \frac{1}{8} > 2^{-3} + 2^{-3} + 2^{-3} + 2^{-3} = \sum_{r=4}^{7} 2^{-3} = \sum_{r=2^2}^{2^3-1} 2^{-3}. $$ In other words, we have $$ \sum_{k=1}^{\infty} \frac{1}{k} \ge \sum_{j=1}^{\infty} \left( \sum_{r=2^{j-1}}^{2^{j}-1} 2^{-j} \right), \tag{1}$$ Where the inner sum is the generalized version of the sums above which represent the groups of terms. But the general term of the inner sums are constant with respect to the index of summation (i.e. the summands don't depend on $r$), and so we just have to count the number of terms. Therefore $$ \sum_{r=2^{j-1}}^{2^{j}-1} 2^{-j} = \big((2^{j}-1) - (2^{j-1})\big) 2^{-j} = 2^{j-j} - 2^{-j} - 2^{j-1-j} = 1 - 2^{-j} - 2^{-1} = \frac{1}{2} - 2^{-j} \ge \frac{1}{2}. $$ Plugging this back in at (1), we get $$ \sum_{k=1}^{\infty} \frac{1}{k} \ge \sum_{j=1}^{\infty} \left( \sum_{r=2^{j-1}}^{2^{j}-1} 2^{-j} \right) \ge \sum_{j=1}^{\infty} \frac{1}{2} = \infty.$$
Of course, I really should write all of that out in terms of partial sums, but I think that actually hides some of the intuition. The point is that for each $j$, we associate terms into groups that contain $2^{j}$ terms, where each term in the group is larger than $2^{-j-1}$. Thus each group sums to more than $\frac{1}{2}$. There are infinitely many such terms, so the series diverges.
$\endgroup$
