Una buena fórmula para el Thue–Morse secuencia

Question

El Thue–Morse secuencia$^{[1]}$$\!^{[2]}$ $t_n$ es una infinita secuencia binaria construido por partida con $t_0=0$ y, sucesivamente, anexando el binario complemento de la secuencia obtenida hasta el momento: $$\begin{array}l 0\\ 0&\color{red}1\\ 0&1&\color{red}1&\color{red}0\\ 0&1&1&0&\color{red}1&\color{red}0&\color{red}0&\color{red}1\\ 0&1&1&0&1&0&0&1&\color{red}1&\color{red}0&\color{red}0&\color{red}1&\color{red}0&\color{red}1&\color{red}1&\color{red}0\\ \hline 0&1&1&0&1&0&0&1&1&0&0&1&0&1&1&0&1&0&0&1&0&1&1&\dots\\ t_0&t_1&t_2&t_3&t_4&\dots\!\!\! \end{array}$$

Tiene muchas propiedades interesantes: es aperiódica, cubo libre, muestra de la paridad del número de $1$'s en la representación binaria de un número natural, tiene conexiones a la Fabius función, la función hipergeométrica, etc.

No es una buena fórmula para esta secuencia que sólo utiliza funciones elementales, los coeficientes binomiales y finito suma: $$t_n=\frac43\,\sin^2\left(\frac\pi3\left(n-\sum_{k=1}^n(-1)^{\binom n k}\right)\right)=\operatorname{mod}\left(2n+\sum_{k=1}^n(-1)^{\binom n k},\,3\right).$$ Por desgracia, no pude encontrar una prueba de esta fórmula en cualquier lugar y no podía construir yo mismo. Por lo tanto, estoy pidiendo su ayuda con esto.

Answer 1

Dado cualquier entero $n \ge 0$, vamos a $( n_0, n_1, n_2, \ldots )$ ser su representación binaria, es decir,

$$n = \sum_{i=0}^\infty n_i 2^i, \quad n_i \in \{ 0, 1 \}$$

Deje $P(n) = n_0$ ser la paridad de $n$ $N(n) = \sum\limits_{i=0}^\infty n_i$ el número de bits en esta representación binaria. No es difícil ver $t_n = 1$ cuando y sólo cuando $N(n)$ es impar. es decir, $$t_n = P(N(n))$$

Aviso $$n - \sum_{k=1}^n (-1)^{\binom{n}{k}} = \sum_{k=0}^n \left(1 - (-1)^{\binom{n}{k}}\right) -2 = 2\sum_{k=0}^nP\left(\binom{n}{k}\right) - 2\etiqueta{*1} $$ Para cualquier $0 \le k \le n$, vamos a $(k_0,k_1,k_2,\ldots)$ ser la representación binaria de $k$.
Por Lucas teorema, tenemos $$P\left(\binom{n}{k}\right) = \prod_{i=0}^\infty P\left(\binom{n_i}{k_i}\right)$$

donde $\displaystyle\;\binom{n_i}{k_i}$ debe ser interpretado como $0$ siempre $n_i < k_i$.

Para que el sumando en RHS de $(*1)$ a ser distinto de cero,

• Para los $i$ donde $n_i = 1$, $k_i$ puede ser $0$ o $1$.
• Para los $i$ donde $n_i = 0$, $k_i$ sólo puede ser $0$.

Esto significa que en el extremo derecho de la suma de $(*1)$, exactamente $2^{N(n)}$ $P(\cdot)$ contribuye. Esto lleva a

$$\begin{align} & n - \sum_{k=1}^n(-1)^{\binom{n}{k}} = 2^{N(n)+1} - 2 \equiv 2P(N(n)) \pmod 3\\ \implies & \frac43\sin^2\left(\frac{\pi}{3}\left(n - \sum_{k=1}^n (-1)^{\binom{n}{k}}\right)\right) = \frac43\sin^2\left(\frac{2\pi}{3}P(N(n))\right) \stackrel{\color{blue}{\because P(\cdot) = 0\text{ or } 1}}{=} P(N(n)) = t_n \end{align}$$

Answer 2

Una alternativa a prueba. Por el bien de la composición voy a escribir $C(n,k)$ en lugar de $\binom nk$.

Ya sabemos $t_k$ siempre $0$ o $1$, es suficiente para mostrar que $$t_n\equiv 2n+\sum_{k=1}^n(-1)^{C(n,k)}\pmod3\ .\tag{$*$}$$ Se sabe que el Thue-Morse secuencia se define por $$t_0=0\ ,\quad t_{2n}=t_n\ ,\quad t_{2n+1}=1-t_n\ .$$ Es claro que el lado derecho de la $(*)$ satisface la condición inicial, voy a demostrar que también satisface la recurrencia.

---

Lema: $C(2n,2k)\equiv C(n,k)\pmod2$.

Prueba. Contar el número de subconjuntos de tamaño $2k$ en un conjunto de tamaño $2n$ por primera eligiendo $j$ elementos de la primera $n$. Tenemos $$\eqalign{C(2n,2k) &=\sum_{j=0}^{2k}C(n,j)C(n,2 k-j)\cr Y=C(n,k)^2+\sum_{j=0}^{k-1}\bigl(C(n,j)C(n,2 k-j)+C(n,2 k-j)C(n,j)\bigr)\cr &\equiv C(n,k)^2\pmod2\cr &\equiv C(n,k)\pmod2\ .\cr}$$

---

Lema: $bC(a,b)=aC(a-1,b-1)$.

Prueba. Bien conocido. De ello se deduce fácilmente que $$\displaylines{ C(2n,2k-1)\equiv (2k-1)C(2n,2k-1)\equiv2nC(2n-1,2 k-2)\equiv0\pmod2\ ;\cr C(2n+1,2 k)=C(2n,2k)+C(2n,2k-1)\equiv C(n,k)\pmod2\ ;\cr C(2n+1,2 k+1)\equiv(2k+1)C(2n+1,2 k+1)=(2n+1)C(2n,2k)\equiv C(n,k)\pmod2\ .\cr}$$

---

En $(*)$ ahora tenemos $$\eqalign{RHS(2n) &=4n+\sum_{j=1}^{2n}(-1)^{C(2n,j)}\cr &=4n+\sum_{k=1}^n(-1)^{C(2n,2k-1)}+\sum_{k=1}^n(-1)^{C(2n,2)}\cr &=4n+n+\sum_{k=1}^n(-1)^{C(n,k)}\cr &\equiv RHS(n)\pmod3\cr}$$ y $$\eqalign{RHS(2n+1) &=4n+2+\sum_{j=1}^{2n+1}(-1)^{C(2n+1,j)}\cr &=4n+1+\sum_{k=1}^n(-1)^{C(2n+1,2 k)}+\sum_{k=1}^n(-1)^{C(2n+1,2 k+1)}\cr &=4n+1+2\sum_{k=1}^n(-1)^{C(n,k)}\cr &\equiv1-RHS(n)\pmod3\ .\cr}$$ Como se explicó anteriormente, esto completa la prueba.

---

De la observación. Continuar para simplificar el modulo $3$ podemos escribir la fórmula como $$\eqalign{t_n\equiv 2n+\sum_{k=1}^n(-1)^{C(n,k)} &\equiv\sum_{k=1}^n\left(-1+(-1)^{C(n,k)}\right)\cr &\equiv\sum_{\estilo de texto{k=1\en la cima de C(n,k)\ \rm impar}}^n(-2)\cr &\equiv\sum_{\estilo de texto{k=1\en la cima de C(n,k)\ \rm impar}}^n1\cr &\equiv\#\{k\mid 1\le k\le n\ \hbox{y $C(n,k)$ es impar}\}\ .\cr}$$