Bertrand's Postulate

From AoPSWiki

Revision as of 08:45, 18 October 2008 by Valentin Vornicu (Talk | contribs)

(diff) ← Older revision | Current revision (diff) | Newer revision → (diff)

Formulation

Bertrand's postulate states that for any positive integer $n$ , there is a prime between $n$ and $2n-2$ . Despite its name, it is, in fact, a theorem. A more widely known version states that there is a prime between $n$ and $2n$ .

Proof

It is similar to the proof of Chebyshev's estimates in the prime number theorem article but requires a closer look at the binomial coefficient $2n\choose n$ . Assuming that the reader is familiar with that proof, the Bertrand postulate can be proved as follows.

Note that the power with which a prime $p$ satisfying $\frac{2n}3<p\le n$ appears in the prime factorization of $2n\choose n$ is $\left\lfloor\frac{2n}{p}\right\rfloor-2\left\lfloor\frac{n}{p}\right\rfloor=2-2=0$ . Thus,

$\frac{2^{2n}}{(2n+1)}\le{2n\choose n}\le\left(\prod_{p\le\sqrt{2n}}p^{\lfloor\log_p (2n)\rfloor}\right)\cdot\left(\prod_{\sqr...$ .

The first product does not exceed $(2n)^{\sqrt{2n}}$ and the second one does not exceed $4^{\frac {2n}3}$ . Thus,

$\left(\prod_{n<p\le{2n}}p\right)\ge \frac{4^{\frac n3}}{(2n+1)(2n)^{\sqrt {2n}}}$

The right hand side is strictly greater than $1$ for $n\ge 500$ , so it remains to prove the Bertrand postulate for $n<500$ . In order to do it, it suffices to present a sequence of primes starting with $2$ in which each prime does not exceed twice the previous one, and the last prime is above $500$ . One such possible sequence is $2,3,5,7,13,23,43,83,163,317,631$ .

This article is a stub. Help us out by expanding it.

Personal tools

Navigation

Search

Toolbox

Bertrand's Postulate

From AoPSWiki

Formulation

Proof