23
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ Wow! It's really incredible someone figured it out $\endgroup$ – Eduardo Longa Aug 14 '16 at 3:32
  • 9
    $\begingroup$ $4/3\sin^2(\pi/3\,x)$, by the way, is $0$ if $x$ is a multiple of $3$ and $1$ otherwise. $\endgroup$ – Akiva Weinberger Aug 14 '16 at 4:00
  • 2
    $\begingroup$ @Akiva Weinberger Very interesting remark showing that the presence of $\sin^2()$ is quite artificial ! $\endgroup$ – Jean Marie Aug 14 '16 at 7:29
17
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Thanks! I'm curious, did you know this (or an equivalent) formula with binomial coefficients for the T-M sequence before? $\endgroup$ – Vladimir Reshetnikov Aug 14 '16 at 20:44
  • 1
    $\begingroup$ @VladimirReshetnikov No, I don't know that formula with binomial coefficients before. I do have some vague memory that $t_n$ equal to the number of set bits in binary expansion of $n$. What I do is a web search on the connection between the parity of $\binom{n}{k}$ and the number of set bits of $n$ and find the Lucas' theorem. $\endgroup$ – achille hui Aug 14 '16 at 21:21
9
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.