- Proof of Bertrand's postulate
In

mathematics ,Bertrand's postulate (actually atheorem ) states that for each "n" ≥ 2 there is a prime "p" such that "n" < "p" < 2"n". It was first proven byPafnuty Chebyshev , and a short but advanced proof was given bySrinivasa Ramanujan . The gist of the following elementary but involvedproof by contradiction is due toPaul Erds ; the basic idea of the proof is to show that a certainbinomial coefficient needs to have aprime factor within the desired interval in order to be large enough.__TOC__The argument in the proof establishes a contradiction by comparing two facts:

* The binomial coefficient $extstyleinom\{2n\}\{n\}$ is "large" in a precise sense (Lemma 1), and

* If Bertrand's postulate fails for "n", then all of the prime factors of this binomial coefficient are "small" (a combination of Lemma 3 and the negation ofBertrand's postulate ).It is then shown by some extended computation (relying mostly on Lemma 2 and Lemma 4) that the second fact is inconsistent with the first one. Therefore Bertrand's postulate must hold. In order to present the main argument of the proof intelligibly, these lemmas and a few auxiliary claims are proved separately first.**Lemmas and computations****anchor|Lemma 1Lemma 1: A lower bound on the central binomial coefficients****Lemma:**For any integer "n" > 0, we have:$frac\{4^n\}\{2n+1\}\; <\; inom\{2n\}\{n\}.$**Proof:**Applying thebinomial theorem ,:$4^n\; =\; (1\; +\; 1)^\{2n\}\; =\; sum\_\{k\; =\; 0\}^\{2n\}\; inom\{2n\}\{k\}.$Since $extstyleinom\{2n\}\{n\}$ is the largest term in the sum, we have::$4^n\; <\; (2n\; +\; 1)\; inom\{2n\}\{n\},$as desired.**anchor|Lemma 2Lemma 2: An upper bound on prime powers dividing central binomial coefficients**For a fixed prime "p", define "R"("p","n") to be the highest natural number "x", such that "p"

^{"x"}divides $extstyleinom\{2n\}\{n\}.$**Lemma:**For any "p", we have "p"^{"R"("p","n")}≤ 2"n".**Proof:**The exponent of "p" in "n"! is (seeFactorial#Number theory )::$sum\_\{j\; =\; 1\}^infty\; leftlfloor\; frac\{n\}\{p^j\}\; ight\; floor,$so we get:$R(p,n)\; =sum\_\{j\; =\; 1\}^infty\; leftlfloor\; frac\{2n\}\{p^j\}\; ight\; floor\; -\; 2sum\_\{j\; =\; 1\}^infty\; leftlfloor\; frac\{n\}\{p^j\}\; ight\; floor\; =sum\_\{j\; =\; 1\}^infty\; left(leftlfloor\; frac\{2n\}\{p^j\}\; ight\; floor\; -\; 2leftlfloor\; frac\{n\}\{p^j\}\; ight\; floor\; ight).$But each term of the last summation can either be 0 (if "n" / "p"^{"j"}mod 1 < 1/2) or 1 (if "n" / "p"^{"j"}mod 1 ≥ 1/2) and all terms with "j" > log_{"p"}(2"n") are 0. Therefore:$R(p,n)\; leq\; log\_p(2n),$and we get::$p^\{R(p,n)\}\; leq\; p^\{log\_p\{2n\; =\; 2n.$This completes the proof of the lemma.**anchor|Lemma 3Lemma 3: The exact power of a large prime in a central binomial coefficient****Lemma:**For $p\; >\; sqrt\{2n\},$ we have:$R(p,n)\; =\; leftlfloor\; frac\{2n\}\{p\}\; ight\; floor\; -\; 2leftlfloor\; frac\{n\}\{p\}\; ight\; floor.$**Proof:**Using the same sum for "R"("p","n") as in Lemma 2, we see that since "p"^{2}> "2n", in fact only the first term is nonzero; this term is exactly the right-hand side of the above equation.**anchor|Lemma 4Lemma 4: An upper bound on the primorial**We estimate the

primorial function,:$n\#\; =\; prod\_\{p\; leq\; n\}\; p,$where the product is taken over all "prime" numbers "p" less than or equal to "n".**Lemma:**For all "n" ≥ 1, we have "n"# < 4^{"n"}.**Proof:**The proof is bymathematical induction . First the base cases:

* "n" = 1: "n"# is theempty product :::$n\#\; =\; 1\; <\; 4\; =\; 4^1.$

* "n" = 2: 2 is prime:::$2\#\; =\; 2\; <\; 16\; =\; 4^2.$

* "n" > 2 and "n" is even: Since every even number greater than 2 is composite, we have by the induction hypothesis:::$n\#\; =\; (n-1)\#\; <\; 4^\{n-1\}\; <\; 4^n.$

* "n" > 2 is odd. Let "n" = 2"m" + 1 with "m" > 0; then since all the terms in the following binomial expansion are positive we have:::$egin\{align\}4^m\; =\; frac\{1\}\{2\}(1\; +\; 1)^\{2m\; +\; 1\}\; =\; frac\{1\}\{2\}sum\_\{k\; =\; 0\}^\{2m+1\}\; inom\{2m\; +\; 1\}\{k\}\; \backslash \; frac\{1\}\{2\}\; Biggl(inom\{2m\; +\; 1\}\{m\}\; +\; inom\{2m\; +\; 1\}\{m\; +\; 1\}Biggr)\; =\; inom\{2m\; +\; 1\}\{m\}.end\{align\}$:Each prime "p" with "m" + 1 < "p" ≤ 2"m" + 1 divides $extstyleinom\{2m\; +\; 1\}\{m\},$ giving us:::$frac\{(2m\; +\; 1)\#\}\{(m\; +\; 1)\#\}\; =\; prod\_\{p\; >\; m\; +\; 1\}^\{p\; leq\; 2m\; +\; 1\}\; p\; leq\; inom\{2m+1\}\{m\}\; 4^m.$:By induction, ("m" + 1)# < 4^{"m" + 1}, so:::$n\#\; =\; (2m\; +\; 1)\#\; <\; 4^m\; cdot\; (m\; +\; 1)\#\; <\; 4^m\; cdot\; 4^\{m\; +\; 1\}\; =\; 4^\{2m\; +\; 1\}\; =\; 4^n.$Thus the lemma is proved.**Computations**We collect here four numerical claims which come up in the proof. Here "n" is always an integer, and "t" is a real number.

#anchor|Claim 1 If "n" > 5, then $2n/3\; >\; sqrt\{2n\};$

#anchor|Claim 2 If "n" > 0, then 2"n" + 1 < (2"n")^{2};

#anchor|Claim 3 If "n" > 18, then $2\; <\; sqrt\{2n\}/3;$

#anchor|Claim 4 If 2^{"t"}< 8"t", then "t" < 6.To prove 1, square both sides and solve::$frac\{2n\}\{3\}\; >\; sqrt\{2n\}\; quadLeftrightarrowquad\; frac\{4n^2\}\{9\}\; >\; 2n\; quadLeftrightarrowquad\; 4n^2\; -\; 18n\; =\; 2n(2n\; -\; 9)\; >\; 0$and if "n" > 5, both factors are positive, so this is in fact true.

To prove 2, collect the sides together and complete the square::$2n\; +\; 1\; <\; (2n)^2\; quadLeftrightarrowquad\; (2n)^2\; -\; (2n)\; -\; 1\; >\; 0\; quadLeftrightarrowquad\; left(2n\; -\; frac\{1\}\{2\}\; ight)^2\; -\; frac\{5\}\{4\}\; >\; 0.$If "n" > 0 is an integer, then 2"n" ≥ 2, so the left-hand side is indeed always positive.

To prove 3, square both sides::$2\; <\; frac\{sqrt\{2n\{3\}\; quadLeftrightarrowquad\; 36\; <\; 2n\; quadLeftrightarrowquad\; n\; >\; 18.$To prove 4, note that 2

^{6}= 64 > 48 = 8 × 6, so the inequality is true for "t" = 6. Now comparing derivatives::$frac\{d\}\{dt\}\; 2^t\; =\; 2^t\; ln\; 2\; >\; 8\; =\; frac\{d\}\{dt\}\; 8t$for "t" > 6, since then the left side is 64 ln 2, or about 44. Thus 2^{"t"}increases more quickly than 8"t" as well as beginning greater, so remains greater.**Proof of Bertrand's Postulate**Assume there is a

counterexample : an integer "n" ≥ 2 such that there is no prime "p" with "n" ≤ "p" < 2"n".If 2 ≤ "n" < 2048, then "p" can be chosen from among the prime numbers 3, 5, 7, 13, 23, 43, 83, 163, 317, 631, 1259 and 2503 (each being less than twice its predecessor) such that "n" < "p" < 2"n". Therefore "n" ≥ 2048.

There are no prime factors "p" of $extstyleinom\{2n\}\{n\}$ such that:

* 2"n" < "p", because 2"n" is the largest factor;

* "n" ≤ "p" ≤ 2"n", because we assumed there is no such prime number;

* 2"n" / 3 < "p" ≤ "n": by computation 1 we have $p\; >\; sqrt\{2n\}$, so Lemma 3 applies, and by rearranging the inequalities 2"n" / 3 < "p" and "n" ≥ "p" we deduce that "n" / "p" ≥ 1 and 2"n" / "p" < 3. Combining these results, we get::$R(p,n)\; =\; leftlfloor\; frac\{2n\}\{p\}\; ight\; floor\; -\; 2leftlfloor\; frac\{n\}\{p\}\; ight\; floor\; leq\; 2\; -\; 2\; =\; 0.$Therefore, every prime factor "p" satisfies "p" ≤ 2"n" / 3.When $p\; >\; sqrt\{2n\},$ the number $extstyle\; \{2n\; choose\; n\}$ has at most one factor of "p". By Lemma 2, for any prime "p" we have "p"

^{"R"("p","n")}≤ 2"n", so the product of the "p"^{"R"("p","n")}over all other primes is at most $(2n)^\{sqrt\{2n.$ Then, starting with Lemma 1 and decomposing the right-hand side into its prime factorization, these bounds give::$frac\{4^n\}\{2n\; +\; 1\}\; <\; inom\{2n\}\{n\}\; =\; left(prod\_\{p\; le\; sqrt\{2n\; p^\{R(p,n)\}\; ight)\; left(prod\_\{p\; sqrt\{2n^\{p\; le\; 2n/3\}\; p^\{R(p,n)\}\; ight)\; (2n)^\{sqrt\{2n\; prod\_\{p\; 1\}^\{p\; leq\; 2n/3\}\; p\; =\; (2n)^\{sqrt\{2n\; cdot\; lfloor\; 2n/3\; floor\#.$Using Lemma 4, this simplifies::$frac\{4^n\}\{2n\; +\; 1\}\; <\; (2n)^\{sqrt\{2n\; 4^\{lfloor\; 2n/3\; floor\}\; leq\; (2n)^\{sqrt\{2n\; 4^\{2n/3\}.$Clearing the denominator and applying computations 2 and 3::$4^\{n/3\}\; <\; (2n\; +\; 1)(2n)^\{sqrt\{2n\; <\; (2n)^\{2\; +\; sqrt\{2n\; <\; (2n)^\{(4/3)sqrt\{2n.$Taking the logarithm of both sides::$frac\{n\}\{3\}ln\; 4\; <\; frac\{4\}\{3\}sqrt\{2n\}\; ln(2n)\; quadLeftrightarrowquad\; sqrt\{2n\}\; ln\{2\}\; <\; 4\; cdot\; ln(2n).$Substituting 2^{2"t"}for 2"n"::$frac\{2^t\}\{t\}\; <\; 8.$This gives us "t" < 6 by computation 4, and the contradiction::$n\; =\; frac\{2^\{2t\{2\}\; <\; frac\{2^\{2\; cdot\; 6\{2\}\; =\; 2048.$Thus no counterexample to the postulate is possible.Q.E.D. **References**This proof of Bertrand's postulate is based on the one in

Proofs from THE BOOK .

*Wikimedia Foundation.
2010.*

### Look at other dictionaries:

**Bertrand's postulate**— (actually a theorem) states that if n > 3 is an integer, then there always exists at least one prime number p with n < p < 2 n − 2. A weaker but more elegant formulation is: for every n > 1 there is always at least one prime p such that n < p < 2 … Wikipedia**Proof of impossibility**— A proof of impossibility, sometimes called a negative proof or negative result , is a proof demonstrating that a particular problem cannot be solved, or cannot be solved in general. Often proofs of impossibility have put to rest decades or… … Wikipedia**List of mathematics articles (P)**— NOTOC P P = NP problem P adic analysis P adic number P adic order P compact group P group P² irreducible P Laplacian P matrix P rep P value P vector P y method Pacific Journal of Mathematics Package merge algorithm Packed storage matrix Packing… … Wikipedia**Nombre premier de Ramanujan**— En mathématiques, un nombre premier de Ramanujan est un nombre premier qui satisfait un résultat démontré par Srinivasa Ramanujan relatif à la fonction de compte des nombres premiers. Origines et définition En 1919, Ramanujan publia une nouvelle… … Wikipédia en Français**List of number theory topics**— This is a list of number theory topics, by Wikipedia page. See also List of recreational number theory topics Topics in cryptography Contents 1 Factors 2 Fractions 3 Modular arithmetic … Wikipedia**Ramanujan prime**— In mathematics, a Ramanujan prime is a prime number that satisfies a result proven by Srinivasa Ramanujan relating to the prime counting function.Origins and definitionIn 1919, Ramanujan published a new proof [S. Ramanujan, A proof of Bertrand s… … Wikipedia**Paul Erdős**— at a student seminar in Budapest (fall 1992) Born 26 March 1913 … Wikipedia**Proofs from THE BOOK**— is a book of mathematical proofs by Martin Aigner and Günter M. Ziegler. The book is dedicated to the mathematician Paul Erdős, who often referred to The Book in which God keeps all of the most elegant proofs of mathematical theorems. During a… … Wikipedia**List of factorial and binomial topics**— This is a list of factorial and binomial topics in mathematics, by Wikipedia page. See also binomial (disambiguation).*Alternating factorial *Antichain *Beta function *Binomial coefficient *Binomial distribution *Binomial proportion confidence… … Wikipedia**Prime number theorem**— PNT redirects here. For other uses, see PNT (disambiguation). In number theory, the prime number theorem (PNT) describes the asymptotic distribution of the prime numbers. The prime number theorem gives a general description of how the primes are… … Wikipedia