Editing Thue–Morse sequence (section)

=== The Prouhet–Tarry–Escott problem === <!-- This section is linked to from [[Prouhet–Tarry–Escott problem]]. -->
The [[Prouhet–Tarry–Escott problem]] can be defined as: given a positive integer ''N'' and a non-negative integer ''k'', [[Partition of a set|partition]] the set ''S'' = { 0, 1, ..., ''N''-1 } into two [[Disjoint sets|disjoint]] subsets ''S''<sub>0</sub> and ''S''<sub>1</sub> that have equal sums of powers up to k, that is:
:<math> \sum_{x \in S_0} x^i = \sum_{x \in S_1} x^i</math> for all integers ''i'' from 1 to ''k''.

This has a solution if ''N'' is a multiple of 2<sup>''k''+1</sup>, given by:
* ''S''<sub>0</sub> consists of the integers ''n'' in ''S'' for which ''t<sub>n</sub>'' = 0,
* ''S''<sub>1</sub> consists of the integers ''n'' in ''S'' for which ''t<sub>n</sub>'' = 1.

For example, for ''N'' = 8 and ''k'' = 2,
:{{nowrap|1= 0 + 3 + 5 + 6 = 1 + 2 + 4 + 7,}}
:{{nowrap|1= 0<sup>2</sup> + 3<sup>2</sup> + 5<sup>2</sup> + 6<sup>2</sup> = 1<sup>2</sup> + 2<sup>2</sup> + 4<sup>2</sup> + 7<sup>2</sup>.}}

The condition requiring that ''N'' be a multiple of 2<sup>''k''+1</sup> is not strictly necessary: there are some further cases for which a solution exists. However, it guarantees a stronger property: if the condition is satisfied, then the set of ''k''th powers of any set of ''N'' numbers in [[arithmetic progression]] can be partitioned into two sets with equal sums. This follows directly from the expansion given by the [[binomial theorem]] applied to the binomial representing the ''n''th element of an arithmetic progression.

For generalizations of the Thue–Morse sequence and the Prouhet–Tarry–Escott problem to partitions into more than two parts, see Bolker, Offner, Richman and Zara, "The Prouhet–Tarry–Escott problem and generalized Thue–Morse sequences".{{sfnp|Bolker|Offner|Richman|Zara|2016}}