A nice formula for the Thue–Morse sequence

Question

The Thue–Morse sequence$^{[1]}$$\!^{[2]}$ $t_n$ is an infinite binary sequence constructed by starting with $t_0=0$ and successively appending the binary complement of the sequence obtained so far: $$\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}$$

It has many interesting properties: it is aperiodic, cube-free, shows the parity of the number of $1$'s in the binary representation of a natural number, has connections to the Fabius function, the hypergeometric function, etc.

There is a nice formula for this sequence that uses only elementary functions, binomial coefficients and finite summation: $$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).$$ Unfortunately, I could not find a proof of this formula anywhere and could not construct it myself. So, I'm asking for your help with this.

Answer 1

Given any integer $n \ge 0$, let $( n_0, n_1, n_2, \ldots )$ be its binary representation, i.e.

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

Let $P(n) = n_0$ be the parity of $n$ and $N(n) = \sum\limits_{i=0}^\infty n_i$ be the number of set bits in this binary representation. It is not hard to see $t_n = 1$ when and only when $N(n)$ is odd. i.e. $$t_n = P(N(n))$$

Notice $$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\tag{*1} $$ For any $0 \le k \le n$, let $(k_0,k_1,k_2,\ldots)$ be the binary representation of $k$.
By Lucas' theorem, we have $$P\left(\binom{n}{k}\right) = \prod_{i=0}^\infty P\left(\binom{n_i}{k_i}\right)$$

where $\displaystyle\;\binom{n_i}{k_i}$ should be interpreted as $0$ whenever $n_i < k_i$.

In order for the summand in RHS of $(*1)$ to be non-zero,

• For those $i$ where $n_i = 1$, $k_i$ can be $0$ or $1$.
• For those $i$ where $n_i = 0$, $k_i$ can only be $0$.

This means in the rightmost sum of $(*1)$, exactly $2^{N(n)}$ of $P(\cdot)$ contributes. This leads to

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

An alternative proof. For the sake of typesetting I'm going to write $C(n,k)$ instead of $\binom nk$.

Since we know $t_k$ is always $0$ or $1$, it suffices to show that $$t_n\equiv 2n+\sum_{k=1}^n(-1)^{C(n,k)}\pmod3\ .\tag{$*$}$$ It is known that the Thue-Morse sequence is defined by $$t_0=0\ ,\quad t_{2n}=t_n\ ,\quad t_{2n+1}=1-t_n\ .$$ It is clear that the RHS of $(*)$ satisfies the initial condition, I shall show that it also satisfies the recurrence.

---

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

Proof. Count the number of subsets of size $2k$ in a set of size $2n$ by first choosing $j$ elements of the first $n$. We have $$\eqalign{C(2n,2k) &=\sum_{j=0}^{2k}C(n,j)C(n,2k-j)\cr &=C(n,k)^2+\sum_{j=0}^{k-1}\bigl(C(n,j)C(n,2k-j)+C(n,2k-j)C(n,j)\bigr)\cr &\equiv C(n,k)^2\pmod2\cr &\equiv C(n,k)\pmod2\ .\cr}$$

---

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

Proof. Well known. It follows easily that $$\displaylines{ C(2n,2k-1)\equiv (2k-1)C(2n,2k-1)\equiv2nC(2n-1,2k-2)\equiv0\pmod2\ ;\cr C(2n+1,2k)=C(2n,2k)+C(2n,2k-1)\equiv C(n,k)\pmod2\ ;\cr C(2n+1,2k+1)\equiv(2k+1)C(2n+1,2k+1)=(2n+1)C(2n,2k)\equiv C(n,k)\pmod2\ .\cr}$$

---

In $(*)$ we now have $$\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,2k)}\cr &=4n+n+\sum_{k=1}^n(-1)^{C(n,k)}\cr &\equiv RHS(n)\pmod3\cr}$$ and $$\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,2k)}+\sum_{k=1}^n(-1)^{C(2n+1,2k+1)}\cr &=4n+1+2\sum_{k=1}^n(-1)^{C(n,k)}\cr &\equiv1-RHS(n)\pmod3\ .\cr}$$ As explained above, this completes the proof.

---

Observation. Continuing to simplify modulo $3$ we can write the formula as $$\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_{\textstyle{k=1\atop C(n,k)\ \rm odd}}^n(-2)\cr &\equiv\sum_{\textstyle{k=1\atop C(n,k)\ \rm odd}}^n1\cr &\equiv\#\{k\mid 1\le k\le n\ \hbox{and $C(n,k)$ is odd}\}\ .\cr}$$