CLR cover
Previous problem

Problem 10: Thue-Morse Words and Sums of Powers

Next problem

For a finite set of natural numbers $I$ let $\SUM_k(I) = \sum_{i\in I}\,i^k$. Given two finite sets $I$ and $J$ of natural numbers we consider the property $\Dd(n,I,J)$: $$\mbox{for any }k, 0\lt k\lt n,\; \SUM_k(I) = \SUM_k(J),$$ which we examine with regards to sets of positions on the $n$th Thue--Morse word $\tau_n$ of length $2^n$. Namely, the sets are $$T_{\sa{a}}(n)=\{i \mid \tau_n[i]={\tt a}\} \mbox{ and } T_{\sa{b}}(n)=\{j \mid \tau_n[j]=\sa{b}\}.$$

Show that the property $\Dd(n,T_{\sa{a}}(n),T_{\sa{b}}(n))$ holds for any integer $n\gt 1$.

References

  • J. Allouche and J. O. Shallit. The ubiquitous Prouhet-Thue-Morse sequence. In C. Ding, T. Helleseth, and H. Niederreiter, editors, Sequences and Their applications, Proc. SETA 98, pages 1-16, New-York, 1999. Springer-Verlag.