Inequality involving number of binary Lyndon words of length $n$ and $n+1$

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.