This question already has an answer here:

Let's define $t_n$ by the recurrence $$t_0 = 1, \quad t_n = (-1)^n \, t_{\lfloor n/2\rfloor}.\tag1$$ It is easy to see that $|t_n|=1$, and the signs follow the same pattern as the Thue–Morse sequence: $$1,\,-1,\,-1,\,1,\,-1,\,1,\,1,\,-1,\,-1,\,1,\,1,\,-1,\,1,\,-1,\,-1,\,1,\,...\tag2$$ (see this question for an example of a non-recursive formula for $t_n$).

Now, define: $$\mathcal{S}(m, n)=\sum_{k=0}^{2^n-1}t_k\,k^m, \quad \color{gray}{m,\,n\in\mathbb{Z}^+.}\tag3$$ Computing some values of this sum immediately leads to the following conjecture:

$$\text{For all }\, n>m,\,\,\mathcal{S}(m, n)=0.\tag{$\diamond$}$$

(e.g. for $m=2$ and $n=3$ we have $0-1-4+9-16+25+36-49=0$).

How can we prove it? Is it a known result?


marked as duplicate by Vladimir Reshetnikov, Community Apr 5 '18 at 21:48

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.