# Periodic sequences resulting from a summation over the Thue–Morse sequence

Let $s_2(n)$ denote the sum of digits of $n$ in base-2 (OEIS sequence A000120), and $t_n=(-1)^{s_2(n)}$. Note that $t_n$ is the signed Thue–Morse sequence (OEIS sequence A106400), satisfying the recurrence $$t_0=1,\quad\,t_n=(-1)^n\,t_{\lfloor n/2\rfloor}.\tag1$$ Also, $$t_n=\operatorname{mod}\left(\!2n+\sum_{k=1}^n(-1)^{\binom n k},\,3\!\right).\tag2$$ Now, consider the family of sequences $$u^{(m)}_n=\left|\sum_{k=0}^n\binom{m+n-k}m\,t_k\right|,\tag3$$ where $m$ is the index of a sequence within the family, and $n$ is the index of an element within the sequence. These sequences can be seen as iterated partial summations of the original sequence $t_n,$ with their signs dropped.

It appears that each sequence $u^{(m)}_n$ is periodic with period $2^{m+1}$, i.e. $$u^{(m)}_{n+2^{m+1}}=u^{(m)}_n,\tag4$$ and the sum of its elements in each period $$\sum_{n=0}^{2^{m+1}-1}u^{(m)}_n=2^{\binom{m+1}2},\tag5$$ the largest element(s) being $$\max_{n\ge0}\,u^{(m)}_n=2^{\binom m2}.\tag6$$ How can we prove that?

Update: It also appears that, for $m>0,$ each period has $2^m-m+1$ distinct elements, has $m+1$ elements equal to $0$, $m+1$ elements equal to $2^{\binom m2}$; all other values, if present at all, occur exactly twice, positioned symmetrically around the largest elements; for each value $k$ present, the value $2^{\binom m2}-k$ is also present.

• Also, it looks like the shape of each period resembles the shape of the Fabius function, and the resemblance becomes closer as $m$ increases. – Vladimir Reshetnikov May 17 '18 at 19:15

Here is a partial solution, that shows the desired periodicity conditionally on some two combinatorial identities (denoted (8a) and (8b)) below.

Let $$F_m(x)=\binom{x+m}{m}$$ and $$v^{(m)}_n=\sum_{k=0}^nF_m(n-k)t_k$$ (so that your $$u^{(m)}_n$$ is $$|v^{(m)}_n|$$). Using the identity $$t_n=(-1)^n\,t_{\lfloor n/2\rfloor}$$ and decomposing the main sum into two halves, one over odd indices and the other on even indices, one obtains :

$$v^{(m)}_n= \left\lbrace \begin{array}[ll] \\ t_q+\sum_{k=0}^{q-1}\big(F_m(2q-2k)-F_m(2q-2k-1)\big)t_k &\textrm{when } \,n\ \textrm{is even},\, n=2q \\ \sum_{k=0}^{q}\big(F_m(2q+1-2k)-F_m(2q-2k)\big)t_k &\textrm{when } \,n\ \textrm{is odd},\, n=2q+1 \\ \end{array}\right.\tag{7}$$

When $$m=0$$, $$F_0$$ is constant equal to $$1$$, and we deduce from (7) that $$v^{(0)}_n=t_q$$ when $$n=2q$$ and $$0$$ when $$n=2q+1$$. This already shows that all your conjectures hold when $$m=0$$.

Next, assume $$m\gt 0$$. Assume the identities

$$F_m(2x)-F_m(2x-1)=2^{m-1}F_m(x)+\sum_{d=2}^{\lfloor \frac{m}{2} \rfloor +1} G(d,m)F_{m-d}(x) \tag{8a}$$

and

$$F_m(2x+1)-F_m(2x)=2^{m-1}F_m(x)+\sum_{d=2}^{\lfloor \frac{m+1}{2} \rfloor} H(d,m)F_{m-d}(x) \tag{8b}$$

where

$$G(m,d)=\frac{(-1)^{d-1}}{2} \frac{m2^m}{(d-1)2^{d-1}} \binom{m-d}{d-2} \tag{9a}$$

and

$$H(m,d)=\frac{(-1)^{d-1}}{2^{d-1}} \binom{m-d}{d-1} \tag{9b}$$

Combining (8a) and (8b) with (7), one deduces

$$v^{(m)}(2n)=2^{m-1}v^{(m-1)}(n)+\sum_{d=2}^{\lfloor \frac{m}{2} \rfloor +1} G(d,m)v^{(m-d)}(n) \tag{10a}$$

and

$$v^{(m)}(2n+1)=2^{m-1}v^{(m-1)}(n)+\sum_{d=2}^{\lfloor \frac{m+1}{2} \rfloor} H(d,m)v^{(m-d)}(n) \tag{10b}$$

By induction, we see that for each $$m$$ there is a map $$w^{(m)} : [|0..(2^{m+1}-1)|] \to {\mathbb Z}$$, such that

$$v^{(m)}(2^{m+1}q+r)=w^{(m)}(r)t_q \tag{11}$$

In fact, the sequence of maps $$w^{(m)}$$ is defined inductively by the base case

$$w^{(0)}(0)=1, w^{(0)}(1)=0 \tag{12}$$

and the induction relations

$$w^{(m)}(2s)=2^{m+1}w^{(m-1)}(s)+\sum_{d=2}^{\lfloor \frac{m}{2} \rfloor +1} G(d,m)w^{(m-d)}(s) \tag{13a}$$

and

$$w^{(m)}(2s+1)=2^{m+1}w^{(m-1)}(s)+\sum_{d=2}^{\lfloor \frac{m+1}{2} \rfloor} H(d,m)w^{(m-d)}(s) \tag{13b}$$