Desigualdad que implica el número de palabras binarias de Lyndon de longitud $n$ y $n+1$

Question

Dejemos que $f(n)$ sea el número de palabras binarias de Lyndon de longitud $n$ . Esta secuencia viene dada por la entrada OEIS A001037 . ¿Es cierto que $2f(n) \ge f(n+1)$ para todos los positivos $n$ ?

He encontrado una fórmula general para calcular $f(n)$ : $$ f(n) = \frac{1}{n} \sum_{d \mid n} \mu(n/d) 2^d. $$ La simetría también nos permite reescribirlo de otra manera: $$ f(n) = \frac{1}{n} \sum_{d \mid n} \mu(d) 2^{n/d}. $$ Aquí $\mu(x)$ es el Función Möbius y $n$ es un número entero positivo (el caso $n=0$ pueden ser tratados por separado). Es posible sustituir estas identidades en la desigualdad anterior y realizar algunas simplificaciones, pero no parece ir a ninguna parte. Se agradece cualquier ayuda.

EDIT: Mi fórmula original era incorrecta, olvidé el factor de $1/n$ delante de la suma.

Answer 1

Paso 1: Para $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} $$

Prueba: Para el límite superior, $$ 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} $$ Si $d \mid n$ , $d < n$ y $\left( \dfrac{n}{d} \right) = 1$ entonces $\dfrac{n}{d}$ tiene al menos dos divisores primos distintos, lo que implica que $\dfrac{n}{d} \geqslant 6$ es decir $d \leqslant \dfrac{n}{6}$ . Así, $(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}$ .

Para el límite inferior, $$ 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} $$ Si $d \mid n$ , $d < n$ y $\left( \dfrac{n}{d} \right) = -1$ entonces $\dfrac{n}{d}$ tiene al menos un divisor primo, lo que implica que $\dfrac{n}{d} \geqslant 2$ es decir $d \leqslant \dfrac{n}{2}$ . Así, $(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}$ . Por lo tanto, (1) se mantiene.

Paso 2: $2f(n) \geqslant f(n + 1)$ se mantiene para $n \geqslant 15$ .

Prueba: Por (1. 1), basta con demostrar que $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}$ . Porque $$ 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}, $$ y $2^{\frac{n + 1}{4}} \geqslant n + 1$ para $n \geqslant 15$ entonces $$ \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}. $$ Por lo tanto, $2f(n) \geqslant f(n + 1)$ se mantiene para $n \geqslant 15$ .

Paso 3: $2f(n) \geqslant f(n + 1)$ se mantiene para $0 \leqslant n \leqslant 14$ .

Prueba: Mirando hacia arriba en A001037 lo verifica.

Answer 2

$$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,$$

donde $d(n)=O(\sqrt n)$ denota el número de divisores de $n$ . Tenemos $$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}),$$

que tiende a infinito, por lo que basta con comprobar los primeros términos, lo que se puede hacer en OEIS (aunque he hecho un poco de trampa, porque no he buscado la constante en el $O$ notación, pero definitivamente no es tan grande).