Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "Bertrand's Postulate"
 
(9 intermediate revisions by 7 users not shown)
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-2</math>.  Despite its name, it is, in fact, a theorem. A more widely known version states that there is a prime between <math>n</math> and <math>2n</math>.
 +
 
 
==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>\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\choose n</math> is <math>\left\lfloor\frac{2n}{p}\right\rfloor-
+
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\choose n}\le
+
<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
 
\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 18:
 
<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>. Another possible sequence is
−
 
 
−
 
 
−
 
 
−
 
 
−
 
 
−
 
 
−
 
 
−
 
 
−
 
 
  
 +
[[category:Axioms]]
 
{{stub}}
 
{{stub}}
 +
[[category:Mathematics]]

Latest revision as of 07:44, 18 October 2024

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 $\binom{2n}{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 $\binom{2n}{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{\binom{2n}{n}}\le \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_{n<p\le {2n}}p\right)\,.$.

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$. Another possible sequence is This article is a stub. Help us out by expanding it.

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=Bertrand%27s_Postulate&oldid=230144"