Difference between revisions of "Bertrand's Postulate"
m (proofreading) |
|||
| Line 1: | Line 1: | ||
==Formulation== | ==Formulation== | ||
| − | '''Bertrand's postulate''' states that for any [[positive integer]] <math>n</math>, there is a [[prime number|prime]] between <math>n</math> and <math>2n</math>. Despite its name, it is in fact a theorem. | + | '''Bertrand's postulate''' states that for any [[positive integer]] <math>n</math>, there is a [[prime number|prime]] between <math>n</math> and <math>2n</math>. Despite its name, it is, in fact, a theorem. |
==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\choose n</math>. Assuming that the reader is familiar with that proof, the Bertrand postulate can be proved as follows. | 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\choose n</math>. Assuming that the reader is familiar with that proof, the Bertrand postulate can be proved as follows. | ||
| Line 11: | Line 11: | ||
\left(\prod_{\sqrt{2n}<p\le\frac{2n}3}p\right)\cdot | \left(\prod_{\sqrt{2n}<p\le\frac{2n}3}p\right)\cdot | ||
\left(\prod_{n<p\le {2n}}p\right)\,. | \left(\prod_{n<p\le {2n}}p\right)\,. | ||
| − | </math> | + | </math>. |
The first product does not exceed <math>(2n)^{\sqrt{2n}}</math> and the second one does not exceed <math>4^{\frac {2n}3}</math>. Thus, | The first product does not exceed <math>(2n)^{\sqrt{2n}}</math> and the second one does not exceed <math>4^{\frac {2n}3}</math>. Thus, | ||
| Line 17: | Line 17: | ||
<math>\left(\prod_{n<p\le{2n}}p\right)\ge \frac{4^{\frac n3}}{(2n+1)(2n)^{\sqrt {2n}}}</math> | <math>\left(\prod_{n<p\le{2n}}p\right)\ge \frac{4^{\frac n3}}{(2n+1)(2n)^{\sqrt {2n}}}</math> | ||
| − | The right hand side is strictly greater than <math>1</math> for <math>n\ge 500</math>, so it remains to prove the Bertrand postulate for <math>n<500</math>. In order to do it, it suffices to present a sequence of primes starting with <math>2</math> in which each prime does not exceed twice the previous one and the last prime is above <math>500</math>. One such possible sequence is | + | The right hand side is strictly greater than <math>1</math> for <math>n\ge 500</math>, so it remains to prove the Bertrand postulate for <math>n<500</math>. In order to do it, it suffices to present a sequence of primes starting with <math>2</math> in which each prime does not exceed twice the previous one, and the last prime is above <math>500</math>. One such possible sequence is |
<math>2,3,5,7,13,23,43,83,163,317,631</math>. | <math>2,3,5,7,13,23,43,83,163,317,631</math>. | ||
Revision as of 13:47, 6 July 2006
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.
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.
