First sums of the Thue-Morse sequence

Question

Let $t_n$ denote the $n^{\rm th}$ element of the Thue-Morse sequence, i.e., $t_n$ begins $$ 0,1,1,0,1,0,0,1,\ldots $$ The first differences of this series are present in the OEIS as entry A029883. This sequence begins $$ 1, 0, -1, 1, -1, 0, 1, 0,\ldots $$ I am however interested in the first sums of the Thue-Morse sequence, i.e., the sequence $s_n$ such that $s_n=t_n+t_{n-1}$ for all $n\geq1$. I have found no reference to this sequence in the OEIS. For info, $s_n$ begins: $$ 1, 2, 1, 1, 1, 0, 1, 2, \ldots $$ It is easy to find some ''basic'' properties of this sequence based on those of $t_n$, but I was wondering whether there have already been some more in-depth studies about it, like for the ''first differences'' sequence.

Answer 1

First of all, the Thue-Morse sequence $(t_n)_{n\ge0}$ is defined by the recurrence:

• $t_0=0$;
• $t_{2n}=t_n$; and
• $t_{2n+1}=1-t_n$.

Thus, to calculate $s_n=t_n+t_{n-1}$ it is natural to separate the cases when $n$ is even and odd.

If $n=2k$ then $s_n=t_{2k}+t_{2k-1}=t_k+(1-t_{k-1})=1+(t_k-t_{k-1})$, so this is essentially the same as the first difference sequence.

If $n=2k+1$ then $s_n=t_{2k+1}+t_{2k}=(1-t_k)+t_k=1$ is constant, so this is uninteresting.

Thus, my guess is that studying the first sum sequence is essentially equivalent to studying the first difference sequence, which is why there isn't much literature on it.

Answer 2

Warning. I considered the sequence $t_n + t_{n+1}$ instead of $t_n + t_{n-1}$, which is not defined for $n = 0$, but it is easy to make the translation.

It is shown in $[1]$ that the shift of a $q$-automatic sequence is $q$-automatic and that the sum of two $q$-automatic sequences is $q$-automatic. Since $t_n$ is $2$-automatic, it follows that $s_n$ is $2$-automatic.

In this specific case, it is not too difficult to obtain the corresponding automata. Here is the automaton for $t_n$

$\qquad$

and the one for the shifted sequence $t_{n+1}$ (the initial state is $1$)

$\qquad$

Combinining the two automata gives

$\qquad$

which leads to the automaton for $s_n$ by adding the outputs (the initial state is $1$)

$\qquad$

For instance, for $n = 21$, the binary expansion is $10101$, and since $1 \cdot 10101 = 4$, one gets $s_{21} = 2$. Indeed, \begin{align} t &= 01101001100101101001011001101001 \dotsm \\ s &= 121110121011121110111\color{red}{2}101211101 \dotsm \end{align} You can certainly find many properties of $s_n$ from the knowledge of this automaton.

EDIT. In particular, if $n$ is even, then $s_n = 1$. If you consider only the odd positions, that is, the sequence $s_{2k+1}$, you obtain the OEIS sequence A316826 $$ 210201210120210201202101 \dotsm $$ obtained by removing the initial $3$ in the image of $3$ by iteration of the morphism $0 \to 02$, $1 \to 1012$, $2 \to 102012$ and $3 \to 32$.

$[1]$ S. Lehr, Sums and rational multiples of $q$-automatic sequences are $q$-automatic. Theoret. Comput. Sci. 108 (1993), no. 2, 385--391.