Proizvolov's identity
In mathematics, Proizvolov's identity is an identity concerning sums of differences of positive integers. The identity was posed by Vyacheslav Proizvolov as a problem in the 1985 All-Union Soviet Student Olympiads.[1]
To state the identity, take the first 2N positive integers,
- 1, 2, 3, ..., 2N − 1, 2N,
and partition them into two subsets of N numbers each. Arrange one subset in increasing order:
Arrange the other subset in decreasing order:
Then the sum
is always equal to N2.
Example
[edit]Take for example N = 3. The set of numbers is then {1, 2, 3, 4, 5, 6}. Select three numbers of this set, say 2, 3 and 5. Then the sequences A and B are:
- A1 = 2, A2 = 3, and A3 = 5;
- B1 = 6, B2 = 4, and B3 = 1.
The sum is
which indeed equals 32.
Proof
[edit]A slick proof of the identity is as follows. Note that for any , we have that :. For this reason, it suffices to establish that the sets and : coincide. Since the numbers are all distinct, it therefore suffices to show that for any , . Assume the contrary that this is false for some , and consider positive integers . Clearly, these numbers are all distinct (due to the construction), but they are at most : a contradiction is reached.
Notes
[edit]- ^ Savchev & Andreescu (2002), p. 66.
References
[edit]- Savchev, Svetoslav; Andreescu, Titu (2002), Mathematical miniatures, Anneli Lax New Mathematical Library, vol. 43, Mathematical Association of America, ISBN 0-88385-645-X.
External links
[edit]- Proizvolov's identity at cut-the-knot.org
- A video illustration (and proof outline) of Proizvolov's identity by Dr. James Grime