# Set of integers with equal sums of powers

Define a sequence $(A_n,B_n)_{n\geq 1}$ as follows : start with $(A_1,B_1)=(\lbrace 1 \rbrace,\lbrace 2 \rbrace)$ and for $n\geq 1$, $A_{n+1}=A_n \cup (2^n+B_n),B_{n+1}=B_n \cup (2^n+A_n)$. Thus, for example, $(A_2,B_2)=(\lbrace 1,4\rbrace,\lbrace 2,3 \rbrace)$, $(A_3,B_3)=(\lbrace 1,4,6,7\rbrace,\lbrace 2,3,5,8 \rbrace)$ etc. It is easy to see by induction that $(A_n,B_n)$ is a partition of $[1..2^n]$.

Question : is it true that for any integer $k$ between $0$ and $n-1$ inclusive, the numbers $a_k=\sum_{t\in A_n} t^k$ and $b_k=\sum_{t\in B_n} t^k$ are equal ?

My thoughts : If $a_k$ and $b_k$ are equal, they will both be equal to $\frac{a_k+b_k}{2}=\frac{\sum_{j=1}^{2^n} j}{2}$. If we put $x=2^n$, one has $a_0=b_0=\frac{x}{2}$, $a_1=b_1=\frac{x(x+1)}{4}$, $a_2=b_2=\frac{x(2x^2+3x+7)}{12}$, $a_3=b_3=\frac{x(x+1)(x^2+x+6)}{8}$. Not sure how to go on from there.

• In $A_{n+1}=A_n \cup (2^n \color{red}{+}B_n)$ does the $+$ mean add this value to each element ? ... so $A_2= \{1,4 \}$ & $B_2= \{ 2,3 \}$ is this right ? ... $a_k,b_k$ are defined as polynomials , but talk in terms of them being numbers ? I am confused ... apologies in advance, if you were trying to earn the tumble weed badge. – Donald Splutterwit Jul 8 '17 at 18:03
• @DonaldSplutterwit I added some clarification into the text. $a_k$ are $b_k$ are not defined as polynomials, they are just defined as functions of $n$ (but conjecturally they are polynomials in $2^n$) – Ewan Delanoy Jul 8 '17 at 18:09
• Thanks Ewan ... you question has suddenly sprung to life after 3 hours of looking like tumble weed ... I will look at Ronald's answer – Donald Splutterwit Jul 8 '17 at 18:12

## 1 Answer

First we show that if we have two sets of numbers $A_n$ and $B_n$ with the property that $$\sum_i a_i^k = \sum_i b_i^k ~~~~~~\text{for all}~ 0\leq k<n$$ than we can construct two other sets $A_n'$ and $B_n'$ with the same property by adding a constant integer $\Delta$ to every element, so that we get $A_n'=A_n+\Delta$ and $B_n'=B_n+\Delta$. This follows from the fact that for $k <n$ we find: $$\sum_i (a_i + \Delta)^k = \sum_i \sum_l \binom{k}{l} a_i^l \Delta^{k-l} = \sum_l \binom{k}{l} \Delta^{k-l} \sum_i a_i^l = \sum_l \binom{k}{l} \Delta^{k-l} \sum_i b_i^l = \sum_i (b_i + \Delta)^k$$ where we used the binomial expansion and the property for values $l \leq k <n$.

So if we now create the sets $A_{n+1}=A_n \cup \left( B_n+\Delta \right)$ and $B_{n+1}=B_n \cup \left( A_n+\Delta \right)$, they will automatically also have this property for all $k<n$, because it is true for the combination $(A_n,B_n)$ as well as for $(A_n+\Delta,B_n+\Delta)$. So we only need to show that the sets $A_{n+1}$ and $B_{n+1}$ also have this property for $k=n$.

This can be shown in a similar fashion: $$\sum_i a_i^n + \sum_i (b_i + \Delta)^n = \sum_i a_i^n + \sum_i \sum_{l=0}^n \binom{n}{l} b_i^l \Delta^{n-l} =$$ $$=\sum_i a_i^n + \sum_i b_i^n + \sum_{l=0}^{n-1} \binom{n}{l} \Delta^{n-l} \sum_i b_i^l =$$ $$=\sum_i b_i^n + \sum_i a_i^n + \sum_{l=0}^{n-1} \binom{n}{l} \Delta^{n-l} \sum_i a_i^l =$$ $$= \sum_i b_i^n + \sum_i \sum_{l=0}^n \binom{n}{l} a_i^l \Delta^{n-l} = \sum_i b_i^n + \sum_i (a_i + \Delta)^n$$ which concludes the proof by induction.

Note that the elements in both sets do not need to be different but can appear multiple times, and that also 0 would be an allowed element. What is important is that the number of elements in both sets is the same.

PS. In order to keep the expressions readable I left out most of the summation limits