Bertrand's postulateBertand's Postulate states that if n is an integer greater than 3, then there is at least one prime between n and 2n-2. It is often stated in the weaker, but perhaps more elegant form: If n is a positive integer, then there is a prime p with n < p ≤ 2n.
In 1845 Bertrand verified this for n less than 3,000,000, and in 1850 Tchebychef gave the first complete proof. In 1932 Erdös gave a much nicer proof using the binomial coefficients, which is the basis of the proof in most modern texts (for example, theorem 418 of [HW79]). This proof can be modified to prove that for any positive integer k, there is a number N such that for all n > N, there are k primes between n and 2n.
Notice Bertrand's postulate tells us that for any prime p, there is another prime less than 2p, so we have the weak result that the nth prime pn is at most 2n. This gives us the following way to create a formula for the nth prime: Let r be any integer greater than one, then let a be the sum
p1r-1 + p2r-4 + p3r-9 + ... + pnr - n2 + ...The nth prime is given by
pn = floor(rn2a) - r2n-1floor(r (n-1)2a)This is cute, but computationally useless.