Fibonacci Structure in Harmonic Series Partitions

A few years ago when I was in high school I was playing around with the harmonic series and noticed some correspondences to the Fibonacci sequence. My original observation was cute but the math it led to was genuinely satisfying.

The Observation

I was playing around with the harmonic series and started greedily grouping terms such that their sum exceeded some threshold τ. I found that when I set this threshold to 0.5, the number of terms in each group followed the Fibonacci sequence, though this pattern broke down around the 8^th term (of the Fibonacci sequence).

Deriving the Optimal Threshold

We begin by noting that the harmonic sum of will always be greater than since uses left-endpoint rectangles which always sit above the strictly decreasing .

By definition of the Euler-Mascheroni constant γ.

The harmonic sum for the first n terms can thus be approximated as Consider an arbitrary group starting at n containing k terms (). For large n, the sum of terms can be represented as the difference of H(x) for the upper and lower bound of the group as such:

We want to obtain a threshold such that the resulting k is a part of the fibonacci sequence.

The growth factor of the Fibonacci sequence is . Consider two consecutive partitions of the harmonic series, we set the growth factor of the sizes of the consecutive partitions to and then solve for the optimal threshold value.

Thus if we greedily partition the harmonic series such that each group’s sum exceeds the threshold , the group sizes grow asymptotically at the Fibonacci rate.

Extracting the Fibonacci Sequence

Using the below python code, we can greedily group consecutive terms of the harmonic series and observe empirically that the sizes of the groups correspond to the fibonacci sequence:

from fractions import Fraction
import math

phi = (1 + math.sqrt(5)) / 2

def harmonic_groups(num_terms, threshold=math.log(phi)):

    pos = 1

    for _ in range(num_terms):

        total = Fraction(0)

        size = 0

        while total ⇐ threshold:

            total += Fraction(1, pos)

            pos += 1

            size += 1

        yield size

print(”,”.join(map(str, list(harmonic_groups(25)))))

The above code produces this sequence: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025.

Empirical Result

Group sizes growing asymptotically at the Fibonacci rate when τ = ln(φ) is apparent from the analysis above. What’s surprising is what happens empirically: the group sizes appear to perfectly corresopnd to the Fibonacci numbers. Whether this holds for all n is unproved and is the more interesting open question.