It presents a surprisingly simple proof (see below). However, it depends on the following statement, which I admit I do not understand:

"Bertrand's Postulate is essentially equivalent to the statement that the first 2k integers can always be arranged in k pairs so that the sum of the entries in each pair is a prime",

Could somebody please help me by clarifying it?

The proof:

Theorem 1. The integers {1, 2, ..., 2k} can be arranged into k disjoint pairs so that the sums of the elements in each pair is prime.
Proof. We prove this by complete induction. The assertion is true when k=1 since 3 is prime. Now consider the set of integers {1, 2, ..., 2k}, and assume that all the sets {1, 2, ..., 2j} have been successfully paired where j is any integer in the range 0 < j < k. We begin by trying to pair 2k with some other number. The possible pairs are (j, 2k) with 0 < j < 2k. The sums of these pairs are all the integers from 2k+1 to 4k-1. Since 2 (2k+1) -2 > 4k-1 Bertrand's Postulate insures that one of these numbers, say 2k+m, is a prime. But m is odd, so the set {m, m+1, ..., 2k-1, 2k} has an even number of elements. This set can be paired so that the sum of the elements in each pair is the prime 2k+m: just pair m+1 with 2k-1, m+2 with 2k-2, etc. The proof is done because our inductive assumption implies that the initial segment from 1 to m-1 can be paired so that the sum of the elements in each pair is a prime. ¤

Regards

The paper you link to does not, and does not claim to, prove Bertrand's Postulate.

The paper provides a proof that "The integers {1, 2, ..., 2k} can be arranged into k disjoint pairs so that the sums of the elements in each pair is prime" (*). To prove this, they rely on Bertrand's Postulate (BP) and complete induction.

What I find confusing is the statement that BP is "essentially equivalent" to (*). The authors state this at the beginning of their paper, but they make no attempt at proving it and do not state precisely what "essentially equivalent" means. They merely show that Bertrand's Postulate implies (*). I would guess that the converse of this statement (that (*) -> BP) cannot be shown. To me, (*) seems to be a much weeker statement than BP.

If you are interested, a beautiful and easily understood proof of BP (due to Erdos) is presented in "Proofs from the Book" by Aigner and Ziegler.