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.

71544403