# Prime Sums in Pairs

A lovely result that follows with relative ease from Bertrand's Postulate has been proved by L. Greenfield and S. Greenfield and reproduced by D. Galvin:

For \(n > 0\), the set \(\{1, 2, \ldots, 2n\}\) can be partitioned into pairs

\(\{a_{1},b_{1}\}\), \(\{a_{2},b_{2}\}\), ..., \(\{a_{n},b_{n}\}\),

such that for each \(1 \le i \le n\), \(a_{i} + b_{i}\) is a prime.

### Proof

The proof is by induction on \(n\). For \(n = 1\) the result is trivial. For \(n > 1\), let \(p\) be a prime satisfying \(2n \lt p \lt 4n\). Since \(4n\) is not prime we have \(p = 2n+m\) for \(1 \le m \lt 2k\). Pair \(2n\) with \(m\), \(2n-1\) with \(m+1\), and continue up to \(n+\lceil k\rceil\) with \(n+\lfloor k\rfloor\) (this last a valid pair since \(m\) is odd). This deals with all of the numbers in \(\{m, m+1,\ldots,2n\}\); the inductive hypothesis deals with \(\{1,2,\ldots,m-1\}\) (again since \(m\) is odd).

### References

- D. Galvin,
*Ërdos's proof of Bertrand's postulate*, April 2006 - L. Greenfield and S. Greenfield,
__Some problems of combinatorial number theory related to Bertrand's postulate__,*J. Integer Seq.*1 (1998), Article 98.1.2.

|Contact| |Front page| |Contents| |Algebra|

Copyright © 1996-2018 Alexander Bogomolny