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.
 A: 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
