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.

Advertisements

~ by Neil Dickson on August 19, 2009.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

 
%d bloggers like this: