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.
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 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 For any , we have: . For this reason, it suffices to establish that the sets and : coincide. Since the numbers are all distinct, it 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 there are at most of them, which is a contradiction.
Notes
References .
External links Proizvolov's identity at cut-the-knot.org A video illustration (and proof outline) of Proizvolov's identity by Dr. James Grime