# 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

1. D. Galvin, Ërdos's proof of Bertrand's postulate, April 2006
2. 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. 