Jtdylktuy

Let $f(n)$ be the number of binary Lyndon words of length $n$. This sequence is given by OEIS entry A001037. Is it true that $2f(n) ge f(n+1)$ for all positive $n$?

I have found a general formula to calculate $f(n)$:
$$
f(n) = frac{1}{n} sum_{d mid n} mu(n/d) 2^d.
$$
Symmetry also allows us to rewrite it another way:
$$
f(n) = frac{1}{n} sum_{d mid n} mu(d) 2^{n/d}.
$$
Here $mu(x)$ is the Möbius function, and $n$ is a positive integer (the case $n=0$ can be handled separately). It is possible to substitute these identities into the inequality above and perform some simplifications, but it does not seem to go anywhere. Any help is appreciated.

EDIT: My original formula was incorrect, I forgot the factor of $1/n$ in front of the summation.

$$f(n)=frac{1}{n} sum_{d | n} mu(d) 2^{n/d} le frac{ 2^n + d(n)cdot 2^{n/2} }n = frac{ 2^n + O(sqrt{n}cdot 2^{n/2}) }n,$$

where $d(n)=O(sqrt n)$ denotes the umber of divisors of $n$.
We have $$2f(n)!!-!!f(n+1)!ge! frac{ 2^{n+1} + O(sqrt{n}cdot 2^{n/2}) }n !-!frac{ 2^{n+1} + O(sqrt{n+1}cdot 2^{(n+1)/2}) }{n+1}!ge! frac{ 2^{n+1}}{n(n+1)}! - ! O(2^{n/2}),$$

which tends to infinity, thus it is enough to check the first few terms, which can be done in OEIS (though I cheated a bit, because I didn't look up the constant in the $O$ notation, but it's definitely not that big).

Step 1: For $n in mathbb{N}_+$,$$
frac{2^n}{n} - frac{2^{frac{n}{2}}}{2} leqslant f(n) leqslant frac{2^n}{n} + frac{2^{frac{n}{6}}}{6}. tag{1}
$$

Proof: For the upper bound,$$
n f(n) = sum_{d mid n} μleft( frac{n}{d} right) 2^d leqslant 2^n + sum_{substack{d mid n, d < n\μ(n / d) = 1}} 2^d. tag{2}
$$
If $d mid n$, $d < n$ and $μleft( dfrac{n}{d} right) = 1$, then $dfrac{n}{d}$ has at least two distinct prime divisors, which implies $dfrac{n}{d} geqslant 6$, i.e. $d leqslant dfrac{n}{6}$. Thus $(2) leqslant 2^n + dfrac{n}{6} 2^{frac{n}{6}} Rightarrow f(n) leqslant dfrac{2^n}{n} + dfrac{2^{frac{n}{6}}}{6}$.

For the lower bound,$$
n f(n) = sum_{d mid n} μleft( frac{n}{d} right) 2^d geqslant 2^n - sum_{substack{d mid n, d < n\μ(n / d) = -1}} 2^d. tag{3}
$$
If $d mid n$, $d < n$ and $μleft( dfrac{n}{d} right) = -1$, then $dfrac{n}{d}$ has at least one prime divisor, which implies $dfrac{n}{d} geqslant 2$, i.e. $d leqslant dfrac{n}{2}$. Thus $(3) geqslant 2^n - dfrac{n}{2} 2^{frac{n}{2}} Rightarrow f(n) geqslant dfrac{2^n}{n} - dfrac{2^{frac{n}{2}}}{2}$. Therefore, (1) holds.

Step 2: $2f(n) geqslant f(n + 1)$ holds for $n geqslant 15$.

Proof: By (1. 1), it suffices to prove that $2 left( dfrac{2^n}{n} - dfrac{2^{frac{n}{2}}}{2} right) geqslant dfrac{2^{n + 1}}{n + 1} + dfrac{2^{frac{n + 1}{6}}}{6}$. Because$$
2 left( frac{2^n}{n} - frac{2^{frac{n}{2}}}{2} right) geqslant frac{2^{n + 1}}{n + 1} + frac{2^{frac{n + 1}{6}}}{6} Longleftrightarrow frac{2^{n + 1}}{n(n + 1)} geqslant 2^{frac{n}{2}} + frac{2^{frac{n + 1}{6}}}{6},
$$
and $2^{frac{n + 1}{4}} geqslant n + 1$ for $n geqslant 15$, then$$
frac{2^{n + 1}}{n(n + 1)} geqslant 2^{frac{n + 1}{2}} = 2^{frac{n}{2}} + (sqrt{2} - 1) 2^{frac{n}{2}} geqslant 2^{frac{n}{2}} + frac{2^{frac{n}{2}}}{6} geqslant 2^{frac{n}{2}} + frac{2^{frac{n + 1}{6}}}{6}.
$$
Therefore, $2f(n) geqslant f(n + 1)$ holds for $n geqslant 15$.

Step 3: $2f(n) geqslant f(n + 1)$ holds for $0 leqslant n leqslant 14$.

Proof: Looking up in A001037 verifies this.