Jump to content

Proizvolov's identity

From Wikipedia, the free encyclopedia

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]

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.
[edit]