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 8th 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:
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.
Denote and notice that the sum of the first Fibonacci numbers Then calculate as follows. We start by noticing that
Additionally, there is the Binet formula implying that which pinpoints to be almost precisely Of course,
However, and .
Since but , it isn't surprising that for ANY large enough we have while Therefore, after having cut off the first numbers in step, we cut off the following numbers via the th step.
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 8th term (of the Fibonacci sequence).
Deriving the Optimal Threshold
We begin by noting that the harmonic sum
By definition of the Euler-Mascheroni constant γ.
The harmonic sum for the first n terms can thus be approximated as
We want to obtain a threshold
The growth factor of the Fibonacci sequence is
Thus if we greedily partition the harmonic series such that each group's sum exceeds the threshold
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.