$$\frac{1}{1}+\frac{1}{2}+\frac{1}{3}+ . . . $$
which diverges. This is a well-known, if counterintuitive, result, and there are several curious proofs of it. In this post, we'll take a look at 4 of them.
Proof 1: Clever subdivision
This is perhaps the most common proof of this result, and was the first one to be discovered (in the 14th century).
We split the series into infinitely many parts in a way that doesn't initially make much sense:
$$\Big(\frac{1}{1}\Big)+\Big(\frac{1}{2}\Big)+\Big(\frac{1}{3}+\frac{1}{4}\Big)+\Big(\frac{1}{5}+\frac{1}{6}+\frac{1}{7}+\frac{1}{8}\Big)+\Big(\frac{1}{9}+ . . . $$
We're going to prove that each of these parts is at least \(\frac{1}{2}\), as follows:
$$1\geq \frac{1}{2}$$
$$\frac{1}{2}\geq \frac{1}{2}$$
$$\frac{1}{3}+\frac{1}{4}\geq \frac{1}{4}+\frac{1}{4}=\frac{1}{2}$$
$$\frac{1}{5}+\frac{1}{6}+\frac{1}{7}+\frac{1}{8}\geq \frac{1}{8}+\frac{1}{8}+\frac{1}{8}+\frac{1}{8}=\frac{4}{8}=\frac{1}{2}$$
So we know the series is at least as large as \(\frac{1}{2}+\frac{1}{2}+\frac{1}{2}+...\), which is clearly infinite.
Proof 2: The integral
We can think of this problem geometrically, too, by lining up rectangles of dimensions \(1\times 1, 1\times \frac{1}{2}, ...\) along the \(x\) axis and measuring the resulting area. If we place the curve \(y=\frac{1}{x}\) on top of these rectangles, we get the following diagram:
We can think of this problem geometrically, too, by lining up rectangles of dimensions \(1\times 1, 1\times \frac{1}{2}, ...\) along the \(x\) axis and measuring the resulting area. If we place the curve \(y=\frac{1}{x}\) on top of these rectangles, we get the following diagram:
The portion of the area under the curve \(y=\frac{1}{x}\) from \(x=1\) to \(\infty\) is bounded by the \(x\)-axis and the tops of the rectangles, so it must be strictly less than the area of the rectangles put together. But this is just
$$\int_1^\infty\frac{1}{x}dx$$
which diverges! So the harmonic series does as well.
Proof 3: Rainfall
This proof is much less formal than the other 3 in this list, but the one I find to be the most intuitive.
Suppose we have some varying amount of rainfall each year - the exact distribution doesn't matter as long as it's sufficiently nice. (If you'd like a specific one, say it's uniformly distributed between 70 and 130 cm.)
Let's look at the record rainfall. If we record in lots of different locations (i.e., we look at the average behavior rather than in one specific trial), then we should expect a record to be set on the \(n^\textrm{th}\) day one \(n^\textrm{th}\) of the time. So the number of records set in total is the sum of the harmonic series.
But clearly we never stop having record rainfall - if it was possible to set a record, there's some probability we can exceed that record, so eventually we'll happen to get a larger amount of precipitation. Thus, the harmonic series diverges.
Proof 4: Pathological bases
The previous 3 proofs have been somewhat illuminating as to the behavior of this sequence, and illustrate that it takes exponentially many more terms to get the series to increase by some fixed amount each time (the partial sums do in fact tend towards \(\ln(x)\)). This one comes entirely out of the blue, leaving you confused why it even worked, and provides no insight, but I like it despite (or maybe because) of that. Without further ado:
Suppose we have some number in binary, like \(0.01101\). The typical way to think of this representation mathematically is for each digit to represent a contribution of \(\frac{1}{2}, \frac{1}{4}, ...\) which we add up to get our number. Instead, let's think of numbers in binary as a set of a directions for where to travel on the number line.
When we see "\(0.\)", we know that we're in the unit interval \([0,1]\) (this is the closed interval, because \(0.111...\) and \(0.000...\) are valid). Now we split our interval in two for the next digit, and a \(0\) tells us that we are in the left of those two halves: \([0,0.5]\). We see a \(1\) next, so we know we're in the right half of this interval: namely, \([0.25,0.5]\). We repeat in this manner ad infinitum (where finite binary representations just terminate in infinitely many \(0\)s) to specify a specific point on the number line.
Now, suppose we do the exact same thing, but split up our interval \(\frac{1}{n}\) of the way across on the \(n^\textrm{th}\) time we do it. So if we wanted to represent \(\frac{3}{4}\), we'd first split the interval \([0,1]\) 100% of the way across, thus obviously choosing the left half. So we start with \(0.0\). Now we split our interval (still \([0,1]\)) halfway across, and take the right half: \(0.01\). Now we cut our interval of \([\frac{1}{2},1]\) a third of the way across (i.e. at \(\frac{2}{3}\)) and take the right half, giving us \(0.011\), etc. We'll call such a representation one in harmonic base. Now, we note two things:
Sources
Proofs 1 and 2 I've been aware of for a long time; they're quite common. Proof 3 I first heard at Canada/USA Mathcamp (from a statistician, unsurprisingly), and proof 4 is original.
The image for proof 2 is in the public domain.
$$\int_1^\infty\frac{1}{x}dx$$
which diverges! So the harmonic series does as well.
Proof 3: Rainfall
This proof is much less formal than the other 3 in this list, but the one I find to be the most intuitive.
Suppose we have some varying amount of rainfall each year - the exact distribution doesn't matter as long as it's sufficiently nice. (If you'd like a specific one, say it's uniformly distributed between 70 and 130 cm.)
Let's look at the record rainfall. If we record in lots of different locations (i.e., we look at the average behavior rather than in one specific trial), then we should expect a record to be set on the \(n^\textrm{th}\) day one \(n^\textrm{th}\) of the time. So the number of records set in total is the sum of the harmonic series.
But clearly we never stop having record rainfall - if it was possible to set a record, there's some probability we can exceed that record, so eventually we'll happen to get a larger amount of precipitation. Thus, the harmonic series diverges.
Proof 4: Pathological bases
The previous 3 proofs have been somewhat illuminating as to the behavior of this sequence, and illustrate that it takes exponentially many more terms to get the series to increase by some fixed amount each time (the partial sums do in fact tend towards \(\ln(x)\)). This one comes entirely out of the blue, leaving you confused why it even worked, and provides no insight, but I like it despite (or maybe because) of that. Without further ado:
Suppose we have some number in binary, like \(0.01101\). The typical way to think of this representation mathematically is for each digit to represent a contribution of \(\frac{1}{2}, \frac{1}{4}, ...\) which we add up to get our number. Instead, let's think of numbers in binary as a set of a directions for where to travel on the number line.
When we see "\(0.\)", we know that we're in the unit interval \([0,1]\) (this is the closed interval, because \(0.111...\) and \(0.000...\) are valid). Now we split our interval in two for the next digit, and a \(0\) tells us that we are in the left of those two halves: \([0,0.5]\). We see a \(1\) next, so we know we're in the right half of this interval: namely, \([0.25,0.5]\). We repeat in this manner ad infinitum (where finite binary representations just terminate in infinitely many \(0\)s) to specify a specific point on the number line.
Now, suppose we do the exact same thing, but split up our interval \(\frac{1}{n}\) of the way across on the \(n^\textrm{th}\) time we do it. So if we wanted to represent \(\frac{3}{4}\), we'd first split the interval \([0,1]\) 100% of the way across, thus obviously choosing the left half. So we start with \(0.0\). Now we split our interval (still \([0,1]\)) halfway across, and take the right half: \(0.01\). Now we cut our interval of \([\frac{1}{2},1]\) a third of the way across (i.e. at \(\frac{2}{3}\)) and take the right half, giving us \(0.011\), etc. We'll call such a representation one in harmonic base. Now, we note two things:
- All finite (i.e. eventually all 0s) strings here are rational; each time, we split a rational interval along a point that is a sum of rational multiples of the endpoints.
- Harmonic base has the same property as binary, where \(0.011011111...=0.01110000...\) - that is, infinite \(1\)s roll over to infinite \(0\)s. If we're at the \(n^\textrm{th}\) place in our harmonic representation and start getting \(1\)s, the size of our interval multiplies by \(\frac{n-1}{n}\), then \(\frac{n}{n+1}\), etc., which clearly multiplies to 0 (cancel terms and you'll see that the denominator gets arbitrarily large), so our number is "forced into" the rational point with a terminating representation.
Okay, we made a weird useless way to write numbers. What now?
Choose a real number \(x\) randomly and uniformly from the interval \([0,1]\), and look at the expected number of \(0\)s in its harmonic base representation. Since no matter what our interval is at the \(n^\textrm{th}\) harmonic place, only \(\frac{1}{n}\) of it will generate a \(0\), the expected number of \(0\)s we get will be \(\frac{1}{n}\), so the total number of \(0\)s in \(x\) on average will be
$$\frac{1}{1}+\frac{1}{2}+\frac{1}{3}+ . . . $$
If \(x\) has only finitely many \(0\)s in its harmonic base representation, it must eventually reach its last \(0\) and be all \(1\)s. But we have just shown this means it is rational, and since the rationals are countable, \(x\) will be rational with probability \(0\). Thus our expected value is infinite, and the harmonic series diverges. Q.E.D.
Sources
Proofs 1 and 2 I've been aware of for a long time; they're quite common. Proof 3 I first heard at Canada/USA Mathcamp (from a statistician, unsurprisingly), and proof 4 is original.
The image for proof 2 is in the public domain.
