Difference between revisions of "Bertrand's Postulate"
m (→Formulation) |
(→Proof) |
||
| (One intermediate revision by the same user not shown) | |||
| Line 3: | Line 3: | ||
==Proof== | ==Proof== | ||
| − | It is similar to the proof of Chebyshev's estimates in the [[Prime Number Theorem|prime number theorem]] article but requires a closer look at the [[combinations|binomial coefficient]] <math>2n | + | It is similar to the proof of Chebyshev's estimates in the [[Prime Number Theorem|prime number theorem]] article but requires a closer look at the [[combinations|binomial coefficient]] <math>\binom{2n}{n}</math>. 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 <math>p</math> satisfying <math>\frac{2n}3<p\le n</math> appears in the prime factorization of <math>2n | + | Note that the power with which a prime <math>p</math> satisfying <math>\frac{2n}3<p\le n</math> appears in the prime factorization of <math>\binom{2n}{n}</math> is <math>\left\lfloor\frac{2n}{p}\right\rfloor- |
2\left\lfloor\frac{n}{p}\right\rfloor=2-2=0</math>. Thus, | 2\left\lfloor\frac{n}{p}\right\rfloor=2-2=0</math>. Thus, | ||
| − | <math>\frac{2^{2n}}{(2n+1)}\le{2n | + | <math>\frac{2^{2n}}{(2n+1)}\le{\binom{2n}{n}}\le |
\left(\prod_{p\le\sqrt{2n}}p^{\lfloor\log_p (2n)\rfloor}\right)\cdot | \left(\prod_{p\le\sqrt{2n}}p^{\lfloor\log_p (2n)\rfloor}\right)\cdot | ||
\left(\prod_{\sqrt{2n}<p\le\frac{2n}3}p\right)\cdot | \left(\prod_{\sqrt{2n}<p\le\frac{2n}3}p\right)\cdot | ||
Latest revision as of 21:43, 11 January 2010
Formulation
Bertrand's postulate states that for any positive integer 
, there is a prime between and 
. Despite its name, it is, in fact, a theorem. A more widely known version states that there is a prime between and 
.
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 
. 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 
satisfying 
appears in the prime factorization of is 
. Thus,
.
The first product does not exceed 
and the second one does not exceed 
. Thus,
The right hand side is strictly greater than 
for 
, so it remains to prove the Bertrand postulate for 
. In order to do it, it suffices to present a sequence of primes starting with 
in which each prime does not exceed twice the previous one, and the last prime is above 
. One such possible sequence is
.
This article is a stub. Help us out by expanding it.
