5
$\begingroup$

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?

$\endgroup$
9
$\begingroup$

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.

| cite | improve this answer | |
$\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.