A Property of the Powers of 2
A combinatorial result due to Paul Erdös and John Selfridge has been discussed by R. Honsberger in his In Pólya's Footsteps. The problem was also discussed by Savchev and Andreescu in the wonderful Mathematical Miniatures.
Given a finite collection of numbers
A = {a_{1}, ..., a_{n}},
the sums of different members of A taken by two form another collection
(1)  A_{2} = {a_{i} + a_{j}: a_{i}, a_{j} A, i ≠ j}. 
(Note that the numbers in A, and even more so in A_{2}, are not required to be distinct. Thus, the term "collection" here is used in liew of the more common "multiset". Multiset is similar to set in that the order of its terms is not important; it differs from set in that its terms may come with multiplicities greater than 1. These multiplicities are as important for distinction between multisets as the sets of their elements. If two identical terms in two multisets have different multiplicities, the multisets are different.)
In the definition (1), the two sums a_{i} + a_{j}, with
(1')  A_{2} = {a_{i} + a_{j}: a_{i}, a_{j} A, i < j}. 
For example, if A = {2, 3, 6, 9} and B = {1, 4, 7, 8}, then
A_{2} = {5, 8, 9, 11, 12, 15} and
B_{2} = {5, 8, 9, 11, 12, 15}.
This example also shows that it is possible to have
Theorem
If A_{2} = B_{2} for different A and B, then A and B are of the same size n and, furthermore, n is a power of 2.
The fact that A and B are bound to have the same size in order for
(2)  A_{2} = B_{2} 
to hold is rather obvious. It follows from the observation that the number
Below I include two copies of the same applet to help you verify the second part of the theorem.
(In the left upper corner of the applet, in blue, you see A terms. Each could be modified by clicking a little of its vertical center line. Beneath it, in black, the applet lists the terms of A_{2} in a nondecreasing order. The size of A could be changed in the same manner. The terms of A_{2} could be displayed, if so desired, in a separate window by clicking on the "Pop frame" button. I'll explain the purpose of the two remaining controls  "#summonds" and "Economize" shortly.)
What if applet does not run? 
Now let's turn to the proof of the second part of the theorem: (2) implies
f(x) = x^{a1} + ... + x^{an} = ∑x^{ai} and
g(x) = x^{b1} + ... + x^{bn} = ∑x^{bi},
where i ranges from 1 through n. Squaring gives
[f(x)]^{2}  = (x^{a1} + ... + x^{an})^{2} 
= (x^{a1})^{2} + ... + (x^{an})^{2}  
+ 2(x^{a1 + a2} + x^{a1 + a3} + ... + x^{an1 + an}) 
In other words,
(3)  [f(x)]^{2} = ∑(x^{2})^{ai} + ∑x^{ai + aj}, i ≠ j. 
Or,
(3_{a})  [f(x)]^{2} = ∑(x^{2})^{ai} + 2∑x^{ai + aj}, i < j. 
And similarly,
(3_{b})  [g(x)]^{2} = ∑(x^{2})^{bi} + 2∑x^{bi + bj}, i < j. 
Since, by our assumption, (2) holds and implies
[f(x)]^{2}  [g(x)]^{2} = ∑(x^{2})^{ai}  ∑(x^{2})^{bi}.
Recalling the definition of f(x) and g(x), this is equivalent to
(4)  [f(x)]^{2}  [g(x)]^{2} = f(x^{2})  g(x^{2}). 
Factoring the left hand side, we have
(4')  (f(x) + g(x))(f(x)  g(x)) = f(x^{2})  g(x^{2}). 
After setting h(y) = f(y)  g(y) the latter transforms into
(4'')  (f(x) + g(x))·h(x) = h(x^{2}). 
Assume A and B are not identical, such that f(x) differs from g(x) and, therefore, h(x) is not identically zero. Then, of course, h(x) can be written in the form
(5)  h(x) = (1  x)^{k}p(x), 
where p(x) is not divisible by (1  x), i.e.,
(6) 

and (4'') becomes
(7)  (f(x) + g(x))·p(x) = (1 + x)^{k}p(x^{2}). 
From the definition, f(1) = g(1) = n, so that (7) yields
2n·p(1) = (1 + 1)^{k}p(1),
where p(1) ≠ 0, from which
n = 2^{k1}.
This is the desired identity, and we are almost done, but not quite yet. To better appreciate the remaining step, let's observe that all the derivation above admits a generalization.
Indeed, from the outset we could have formed the collection A_{s} considering the sums of s
∑(x^{s})^{ai}
and another one whose terms are best described as having exponents
[f(x)]^{s}  [g(x)]^{s} = f(x^{s})  g(x^{s}).
With the same definition of h(x), (6) becomes
h(x^{s})  = (1  x^{s})^{k}p(x^{s}) 
= (1  x)^{s}(1 + x + ... + x^{s1})^{k}p(x^{s}), 
and (7) is replaced by
(f^{s1}(x) + f^{s2}g(x) + f^{s3}g^{2}(x) + ... + g^{s1}(x))·p(x) = (1 + x + ... + x^{s1})^{k}p(x^{s}),
where again we substitute x = 1:
sn^{s1}·p(1) = s^{k}p(1),
so that, finally,
n^{s1} = s^{k1}.
Which appears to support a generalization: if A_{s} = B_{s}, then A = B, provided n is a power of s.
The applet above allows one to change s by clicking on the number labeled "#summonds". The general case is different from the case of two summonds in that the tuples
As we saw at the beginning of the page, there does exist an example with
Now let's return to the proof of our theorem.
Assume that (1) holds for two different multisets A and B, as above. Then it is quite obvious that (1) will also hold for
A = {a_{1}, ..., a_{n}, b_{1}+m, ..., b_{n}+m} and
B = {b_{1}, ..., b_{n}, a_{1}+m, ..., a_{n}+m},
for any number m (different from 0). Since (2) holds trivially for
The curious thing is that while the derivation of the generalization did go through, in the absence of specific A and B that satisfy
(A little different construct and modifications are also discussed elsewhere. Powers of 2 have another interesting and unexpected property.)
References
 R. Honsberger, In Pólya's Footsteps, MAA, 1999, pp. 243246.
 S. Savchev, T. Andreescu, Mathematical Miniatures, MAA, 2003, pp. 193196
Generating Functions
 Generating Functions
 A Property of the Powers of 2
 An USAMTS problem with light switches
 Examples with series of figurate numbers
 Euler's derivation of the binary representation
 Examples with finite sums with binomial coefficients
 Fast Power Indices and Coin Change
 Number of elements of various dimensions in a tesseract
 Straight Tromino on a Chessboard
 Ways To Count
 Probability Generating Functions
 Finite Sums of Terms 2^(ni) i^2
 Sylvester's Problem, a Second Look
 Generating Functions from Recurrences
 Binet's Formula via Generating Functions
 Number of Trials to First Success
 Another Binomial Identity with Proofs
Activities Contact Front page Contents Algebra
Copyright © 19962017 Alexander Bogomolny
62686553 