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.

  • $\begingroup$ Also, it looks like the shape of each period resembles the shape of the Fabius function, and the resemblance becomes closer as $m$ increases. $\endgroup$ – 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} $$


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


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


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


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


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


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.