## The Harmonic Series and Beyond

I was going to write a post about AQUA@Home, the cool quantum simulation system you can help with that I’ve been working on at D-Wave, but I’ll leave that for a couple of days and talk about one of the miscellaneous things that I’ve thought about at random.

I’ve known for quite some time that $\sum_{i=1}^n \frac{1}{i}$ (the harmonic series) divergesas n approaches infinity, and more recently, that it scales as $\Theta(\log n)$.  However, $\sum_{i=1}^n \frac{1}{i^2}$ converges, along with any other positive function $O(\frac{1}{i^2})$ being summed.  For a while I had assumed that any function $o(\frac{1}{i})$ would converge, but I learned in my second calculus course at Carleton that $\sum_{i=2}^n \frac{1}{i \log i}$ also diverges.

Several weeks ago, I was curious where the true bound between converging and diverging is, and I seem to have found it.

I started by finding a simple proof of the scaling of the harmonic series, and it goes something like the following.  Let’s assume that n is a power of two:

$\frac{1}{1}+\frac{1}{2}+\frac{1}{3}+\frac{1}{4}+\frac{1}{5}+\frac{1}{6}+\frac{1}{7}+\frac{1}{8}+\frac{1}{9}+\frac{1}{10}+...+\frac{1}{n}$
$>\frac{1}{1}+\frac{1}{2}+\frac{1}{4}+\frac{1}{4}+\frac{1}{8}+\frac{1}{8}+\frac{1}{8}+\frac{1}{8}+\frac{1}{16}+\frac{1}{16}+...+\frac{1}{n}$
$=\frac{1}{1}+\frac{1}{2}+2(\frac{1}{4})+4(\frac{1}{8})+8(\frac{1}{16})+...+\frac{n}{2}(\frac{1}{n})$
$= 1 + \sum_{j=1}^{\log n} \frac{1}{2}$
$= 1 + \frac{1}{2}\log n$

and:

$\frac{1}{1}+\frac{1}{2}+\frac{1}{3}+\frac{1}{4}+\frac{1}{5}+\frac{1}{6}+\frac{1}{7}+\frac{1}{8}+\frac{1}{9}+\frac{1}{10}+...+\frac{1}{n}$
$<\frac{1}{1}+\frac{1}{2}+\frac{1}{2}+\frac{1}{4}+\frac{1}{4}+\frac{1}{4}+\frac{1}{4}+\frac{1}{8}+\frac{1}{8}+\frac{1}{8}+...+\frac{1}{n/2}+\frac{1}{n}$
$=\frac{1}{1}+2(\frac{1}{2})+4(\frac{1}{4})+8(\frac{1}{8})+16(\frac{1}{16})+...+\frac{n}{2}(\frac{1}{n/2})+\frac{1}{n}$
$=\frac{1}{n} + \sum_{j=0}^{\log n - 1} 1$
$= \log n + \frac{1}{n}$

Therefore, $\sum_{i=1}^n \frac{1}{i} \in \Theta(\log n)$.  Using a similar approach, one can show that $\sum_{i=2}^n \frac{1}{i \log i} \in \Theta(\log \log n)$.  Doing this again can show that $\sum_{i=4}^n \frac{1}{i \log i \log \log i} \in \Theta(\log \log \log n)$, and a pattern emerges allowing each one to be expressed in terms of the previous.

The final conclusion:

$\sum_{i=2^k}^n \frac{1}{i \log i \log \log i \log \log \log i ... \log...\log i} \in \Theta(\log...\log n)$

where the number of logs in the last factor and in the scaling is k.  Note that the $2^k$ is just to prevent any of the logarithms from going to zero, so assume $n >> 2^k$.  If any one of the logarithmic factors in the sum has a power greater than one, the series converges, but with them all equal to or less than one, the series still diverges.  In effect, the scaling can get arbitrarily close to $\Theta(1)$, so this appears to be the very brink of divergence.  Some may argue that having a finite k makes it insufficient, since there are theoretically slower-growing functions, but that’s really splitting hairs.