# First sums of the Thue-Morse sequence

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.

• can you find info about $s_n$ based on binary representation of $n$? Commented Feb 26, 2020 at 22:23
• @mathworker21 Can you elaborate? Commented Mar 15, 2020 at 15:11
• The Thue-Morse sequence $t_n = digitsum_2(n) \mod 2$ where $digitsum_b(n)$ is the digital sum of integer $n$ in base $b$. A property of digital sums is that $$digitsum_b(x + y) = digitsum_b(digitsum_b(x) + digitsum_b(y))$$ Try using that.
– vvg
Commented Nov 4, 2020 at 5:14

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.

• Thanks for the detailed answer. Does this approach make it possible to get a recurrence relation for s_n? Note that for the first differences sequence a_n we have a_4n = a_n, a_{4n+1} = a_{2n+1}, a_{4n+2} = 0, and a_{4n+3} = - a_{2n+1}. Commented Aug 4, 2021 at 8:04

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.

• Makes sense, thanks Commented Aug 4, 2021 at 11:37