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 = {a1, ..., an},
the sums of different members of A taken by two form another collection
(1) | A2 = {ai + aj: ai, aj A, i ≠ j}. |
(Note that the numbers in A, and even more so in A2, 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 ai + aj, with
(1') | A2 = {ai + aj: ai, aj A, i < j}. |
For example, if A = {2, 3, 6, 9} and B = {1, 4, 7, 8}, then
A2 = {5, 8, 9, 11, 12, 15} and
B2 = {5, 8, 9, 11, 12, 15}.
This example also shows that it is possible to have
Theorem
If A2 = B2 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) | A2 = B2 |
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 A2 in a nondecreasing order. The size of A could be changed in the same manner. The terms of A2 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) = xa1 + ... + xan = ∑xai and
g(x) = xb1 + ... + xbn = ∑xbi,
where i ranges from 1 through n. Squaring gives
[f(x)]2 | = (xa1 + ... + xan)2 |
= (xa1)2 + ... + (xan)2 | |
+ 2(xa1 + a2 + xa1 + a3 + ... + xan-1 + an) |
In other words,
(3) | [f(x)]2 = ∑(x2)ai + ∑xai + aj, i ≠ j. |
Or,
(3a) | [f(x)]2 = ∑(x2)ai + 2∑xai + aj, i < j. |
And similarly,
(3b) | [g(x)]2 = ∑(x2)bi + 2∑xbi + bj, i < j. |
Since, by our assumption, (2) holds and implies
[f(x)]2 - [g(x)]2 = ∑(x2)ai - ∑(x2)bi.
Recalling the definition of f(x) and g(x), this is equivalent to
(4) | [f(x)]2 - [g(x)]2 = f(x2) - g(x2). |
Factoring the left hand side, we have
(4') | (f(x) + g(x))(f(x) - g(x)) = f(x2) - g(x2). |
After setting h(y) = f(y) - g(y) the latter transforms into
(4'') | (f(x) + g(x))·h(x) = h(x2). |
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)kp(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)kp(x2). |
From the definition, f(1) = g(1) = n, so that (7) yields
2n·p(1) = (1 + 1)kp(1),
where p(1) ≠ 0, from which
n = 2k-1.
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 As considering the sums of s
∑(xs)ai
and another one whose terms are best described as having exponents
[f(x)]s - [g(x)]s = f(xs) - g(xs).
With the same definition of h(x), (6) becomes
h(xs) | = (1 - xs)kp(xs) |
= (1 - x)s(1 + x + ... + xs-1)kp(xs), |
and (7) is replaced by
(fs-1(x) + fs-2g(x) + fs-3g2(x) + ... + gs-1(x))·p(x) = (1 + x + ... + xs-1)kp(xs),
where again we substitute x = 1:
sns-1·p(1) = skp(1),
so that, finally,
ns-1 = sk-1.
Which appears to support a generalization: if As = Bs, 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 = {a1, ..., an, b1+m, ..., bn+m} and
B = {b1, ..., bn, a1+m, ..., an+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. 243-246.
- S. Savchev, T. Andreescu, Mathematical Miniatures, MAA, 2003, pp. 193-196
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^(n-i) 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
- Matching Socks in Dark Room
|Activities| |Contact| |Front page| |Contents| |Algebra|
Copyright © 1996-2018 Alexander Bogomolny
71471744