Number defined by a recursive binary sequence

Question

In a math column in Scientific American many years ago, I encountered a peculiar binary sequence I describe below. Unfortunately I can't find a reference on this, so I would be grateful for any pointers or references.

Let $\mathbb{N}$ be the set of positive integers and let $T = \{2^n: n\in \mathbb{N}\cup \{0\}\}$ denote the set of powers of $2$. Let $\text{m}:\mathbb{N}\to T\cup\{0\}$ be defined by $n\mapsto \max\big(\{0\}\cup \{t\in T: t<n\}\big)$.

We define $a:\mathbb{N}\to\{0,1\}$ recursively by

• $a(1) = 1$, and
• $a(n) = 1-a(n-\text{m}(n))$ for $n\geq 2$.

This sequence starts by $10010110\ldots$ and I recall that it has some peculiar properties such as, no non-empty finite sub-sequence occurs $3$ times in a row.

Question. Is $\sum_{n=1}^\infty 2^{-n}a(n)$ transcendent?

Answer 1

Let $\{t(i)\}_0^\infty$ be the Thue-Morse sequence. (It starts $0,1,1,0,1,0,0,1,\ldots$.).

I claim that your sequence is described by $a(n)=1-t(n-1)$ where $n$ is a positive integer. (It is similar to sequence A010059 in the OEIS, but its index starts at $1$ instead of at $0$.)

The proof is as follows:

For $n=1$, $a(1)=1-t(1-1)=1$. We now consider $n\ge 2$.

From this OEIS link, let $A_k$ denote the first $2^k$ terms of $t$; then $A_0=0$ and for $k\ge 0$, $A_{k+1}=A_k,B_k$, where $B_k$ is obtained from $A_k$ by interchanging $0$'s and $1$'s. That is, $1-t(i)=t(i-2^k)$ where $2^k\le i\le 2^{k+1}-1$. Since $\mathrm{m}(i)$ is the largest power of $2$ less than $i$, then $\mathrm{m}(i+1)=2^k$. Thus, $1-t(i)=t(i-\mathrm{m}(i+1))$. Letting $i=n-1$ yields $1-t(n-1)=t(n-1-\mathrm{m}(n))$. Letting $a(n)=1-t(n-1)$ yields $a(n)=t(n-1-\mathrm{m}(n))=1-(1-t(n-\mathrm{m}(n)-1))=1-a(n-\mathrm{m}(n))$. $\blacksquare$

---

The Prouhet-Thue-Morse constant $0.01101001\ldots$ (in binary) (which is based on the Thue-Morse sequence) was shown to be transcendental by Kurt Mahler in 1929. It follows that the constant formed from your sequence is also transcendental.