Editing Proof of Bertrand's postulate (section)

{{short description|Solved prime-number problem}}
In [[mathematics]], [[Bertrand's postulate]] (now a [[theorem]]) states that, for each <math>n \ge 2</math>, there is a [[prime number|prime]] <math>p</math> such that <math>n<p<2n</math>. First [[conjecture]]d in 1845 by [[Joseph Louis François Bertrand|Joseph Bertrand]],<ref>{{Citation|first=Joseph |last=Bertrand |author-link=Joseph Bertrand |title=Mémoire sur le nombre de valeurs que peut prendre une fonction quand on y permute les lettres qu'elle renferme. |journal=Journal de l'École Royale Polytechnique |issue=Cahier 30 |volume=18 |year=1845 |pages=123–140 |language=fr |url={{Google Books|WTa-qRIWckoC|page=123|plainurl=yes}}}}.</ref> it was first [[mathematical proof|proven]] by [[Chebyshev]], and a shorter but also advanced proof was given by [[Ramanujan]].<ref>{{Citation |first=S. |last=Ramanujan |title=A proof of Bertrand's postulate |journal=Journal of the Indian Mathematical Society |volume=11 |year=1919 |pages=181–182 |url=http://www.imsc.res.in/~rao/ramanujan/CamUnivCpapers/Cpaper24/page1.htm }}</ref>

The following [[elementary proof]] was published by [[Paul Erdős]] in 1932, as one of his earliest mathematical publications.<ref>{{Citation |first=Pál |last=Erdős |title=Beweis eines Satzes von Tschebyschef |journal=Acta Scientarium Mathematicarum (Szeged) |volume=5 | issue=3–4 |year=1932 |pages=194–198 | trans-title=Proof of a theorem of Chebyshev |url=https://users.renyi.hu/~p_erdos/1932-01.pdf | zbl=004.10103 }}</ref> The basic idea is to show that the [[central binomial coefficient]]s must have a [[prime factor]] within the [[interval (mathematics)|interval]] <math>(n, 2n)</math> in order to be large enough. This is achieved through analysis of their factorizations.

The main steps of the proof are as follows. First, one shows that the contribution of every [[prime power]] factor <math>p^r</math> in the prime decomposition of the central binomial coefficient <math>\textstyle\binom{2n}{n}=(2n)!/(n!)^2</math> is at most <math>2n</math>; then, one shows that every prime larger than <math>\sqrt{2n}</math> appears at most once.

The next step is to prove that <math>\tbinom{2n}{n}</math> has no prime factors in the interval <math>(\tfrac{2n}{3}, n)</math>. As a consequence of these bounds, the contribution to the size of <math>\tbinom{2n}{n}</math> coming from the prime factors that are at most <math>n</math> grows [[asymptotic analysis|asymptotically]] as <math>\theta^{\!\;n}</math> for some <math>\theta<4</math>. Since the asymptotic growth of the central binomial coefficient is at least <math>4^n\!/2n</math>, the conclusion is that, [[proof by contradiction|by contradiction]] and for large enough <math>n</math>, the binomial coefficient must have another prime factor, which can only lie between <math>n</math> and <math>2n</math>.

The argument given is valid for all <math>n\ge427</math>. The remaining values of&nbsp;<math>n</math> are verified by direct inspection, which completes the proof.