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.

  • $\begingroup$ 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. $\endgroup$ – Donald Splutterwit Jul 8 '17 at 18:03
  • $\begingroup$ @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$) $\endgroup$ – Ewan Delanoy Jul 8 '17 at 18:09
  • $\begingroup$ Thanks Ewan ... you question has suddenly sprung to life after 3 hours of looking like tumble weed ... I will look at Ronald's answer $\endgroup$ – Donald Splutterwit Jul 8 '17 at 18:12

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.