TITLE: Sums of integer powers similar to Prouhet–Tarry–Escott problem
QUESTION [18 upvotes]: Recall Prouhet–Tarry–Escott problem. Its solution shows that certain sums of powers of integers can be made to vanish simultaneously if their signs are chosen to follow the Thue–Morse sequence, e.g.
$$\sum_{k=0}^{2^4-1}(-1)^{\sigma_2(k)}\,k^n=0\quad\text{for}\;n<4,\quad\text{i.e.}\\
\small
\begin{array}{l}
 0^1+3^1+5^1+6^1+9^1+10^1+12^1+15^1=1^1+2^1+4^1+7^1+8^1+11^1+13^1+14^1 \\
 0^2+3^2+5^2+6^2+9^2+10^2+12^2+15^2=1^2+2^2+4^2+7^2+8^2+11^2+13^2+14^2 \\
 0^3+3^3+5^3+6^3+9^3+10^3+12^3+15^3=1^3+2^3+4^3+7^3+8^3+11^3+13^3+14^3, \\
\end{array}$$
where $\sigma_2(k)$ is the sum of digits of $k$ in base-2.
I am interested in sums of powers of a similar form, but with larger exponents (such that the sum does not vanish anymore). I was able to make a few conjectures:
$$\begin{align}
&\sum _{k=0}^{2^n-1} (-1)^{\sigma _2(k)}\, k^{n+2}\stackrel{\color{gray}?}=\frac{2^{\binom{n}{2}}}{36}\, (-1)^n\, \left(2^n-1\right)\, \left(5\times2^n-4\right)\, (n+2)!\\
\\
&\sum _{k=0}^{2^n-1} (-1)^{\sigma _2(k)}\,k^{n+3}\stackrel{\color{gray}?}=\frac{2^{\binom{n}{2}}}{72}\,(-1)^n \,\left(2^n-1\right)^2\,\left(2\times2^n-1\right)\,(n+3)!\\
\\
&\small\sum _{k=0}^{2^n-1} (-1)^{\sigma_2(k)}\,k^{n+4}\stackrel{\color{gray}?}=\frac{2^{\binom{n}{2}}}{32400}\,(-1)^n\,\left(2^n-1\right)\,\left(143\!\times\! 8^n-307\!\times\!4^n+193\!\times\! 2^n-32\right)\,(n+4)!\end{align}$$
This pattern seems to continue within increasingly complicated polynomials of $2^n$ on the right-hand side. Can you suggest an approach to prove these, and to find a more general formula for an arbitrary exponent $k^{n+p}$?

REPLY [4 votes]: The exponential generating function for $S_{n,m}=\displaystyle\sum_{k=0}^{2^n-1}(-1)^{\sigma_2(k)}k^m$ (w.r.t. $m$) is $$\sum_{m=0}^\infty S_{n,m}\frac{x^m}{m!}=\sum_{k=0}^{2^n-1}(-1)^{\sigma_2(k)}e^{kx}=\prod_{k=0}^{n-1}(1-e^{2^k x})=2^{n(n-1)/2}(-x)^n\exp\sum_{k=0}^{n-1}f(2^k x),$$ where $$f(x)=\log\frac{e^x-1}{x}=\sum_{m=1}^\infty\frac{B_m^+}{m}\frac{x^m}{m!}$$ using the Bernoulli numbers (look at $f'(x)$ to see the expansion). Thus,
\begin{align*}
S_{n,n+p}&=(-1)^n 2^{n(n-1)/2}(n+p)!\ A_p(2^n),
\\A_p(a)&=[x^p]\exp\sum_{m=1}^\infty\frac{a^m-1}{2^m-1}\frac{B_m^+}{m}\frac{x^m}{m!}.
\end{align*}
This gives an algorithmic way to compute $S_{n,n+p}$ for any fixed $p$. Continuing your table,
\begin{align*}
  A_0(a)&=1
\\2A_1(a)&=a-1
\\36A_2(a)&=(a-1)(5a-4)
\\72A_3(a)&=(a-1)^2(2a-1)
\\32400A_4(a)&=(a-1)(143a^3-307a^2+193a-32)
\\64800A_5(a)&=(a-1)^2(2a-1)(19a^2-24a+2)
\\85730400A_6(a)&=(a-1)(5765a^5-19372a^4+22670a^3-10405a^2+1355a+32)
\\342921600A_7(a)&=(a-1)^2(2a-1)(1166a^4-2850a^3+1715a^2+60a-1)
\end{align*}
Observe that $A_p(a)$ is always divisible by $a-1$, and even by $(a-1)^2(2a-1)$ if $p>1$ is odd (because of $B_m^+=0$ for odd $m>1$, and [the g.f. of] $A_p(1/2)$ in closed form).
{"set_name": "stack_exchange", "score": 18, "question_id": 3970629}