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

212 Views Asked by At

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.

1

There are 1 best solutions below

0
On

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} $$