Editing Proof of Bertrand's postulate (section)

==Lemmas in the proof==

The proof uses the following four [[lemma (mathematics)|lemmas]] to establish facts about the primes present in the central binomial coefficients.

===Lemma 1===
For any [[integer]] <math>n>0</math>, we have
:<math>\frac{4^n}{2n} \le \binom{2n}{n}.</math>

'''Proof:''' Applying the [[binomial theorem]],
:<math>4^n = (1 + 1)^{2n} = \sum_{k = 0}^{2n} \binom{2n}{k}=2+\sum_{k = 1}^{2n-1} \binom{2n}{k} \le 2n\binom{2n}{n},</math>
since <math>\tbinom{2n}{n}</math> is the largest term in the sum in the right-hand side, and the sum has <math>2n</math> terms (including the initial <math>2</math> outside the summation).

===Lemma 2===
For a fixed prime <math>p</math>, define <math>R = R(n,p)</math> to be the [[p-adic order|''p''-adic order]] of <math>\tbinom{2n}{n}</math>, that is, the largest [[natural number]] <math>r</math> such that <math>p^r</math> divides <math>\tbinom{2n}{n}</math>.

For any prime <math>p</math>, <math>p^{R }\le 2n</math>.

'''Proof:''' The exponent of <math>p</math> in <math>n!</math> is given by [[Legendre's formula]]
:<math>\sum_{j = 1}^\infty \left\lfloor \frac{n}{p^j} \right\rfloor\!,</math>
so
:<math>R=\sum_{j = 1}^\infty \left\lfloor \frac{2n}{p^j} \right\rfloor - 2\sum_{j = 1}^\infty \left\lfloor \frac{n}{p^j} \right\rfloor=\sum_{j = 1}^\infty \left(\left\lfloor \frac{2n}{p^j} \right\rfloor - 2\!\left\lfloor \frac{n}{p^j} \right\rfloor\right)</math>
But each term of the last summation must be either zero (if <math>n/p^j \bmod 1<1/2</math>) or one (if <math>n/p^j\bmod 1\ge1/2</math>), and all terms with <math>j>\log_p(2n)</math> are zero. Therefore,
:<math>R \le \log_p(2n),</math>
and
:<math>p^R \le p^{\log_p(2n)} = 2n.</math>

===Lemma 3=== 
If <math>p</math> is an [[parity (mathematics)|odd]] prime and <math>\frac{2n}{3} < p \leq n</math>, then <math>R(n,p) = 0.</math>

'''Proof:''' There are exactly two factors of <math>p</math> in the numerator of the expression <math>\tbinom{2n}{n}=(2n)!/(n!)^2</math>, coming from the two terms <math>p</math> and <math>2p</math> in <math>(2n)!</math>, and also two factors of <math>p</math> in the denominator from one copy of the term <math>p</math> in each of the two factors of <math>n!</math>. These factors all cancel, leaving no factors of <math>p</math> in <math>\tbinom{2n}{n}</math>. (The bound on <math>p</math> in the preconditions of the lemma ensures that <math>3p</math> is too large to be a term of the numerator, and the assumption that <math>p</math> is odd is needed to ensure that <math>2p</math> contributes only one factor of <math>p</math> to the numerator.)

===Lemma 4===
An upper bound is supplied for the [[primorial]] function,
:<math>n\#=\prod_{p\,\le\,n}p,</math>
where the product is taken over all ''prime'' numbers <math>p</math> less than or equal to <math>n</math>.

For all <math>n\ge1</math>, <math>n\#<4^n</math>.

'''Proof:''' We use [[Mathematical induction#Complete (strong) induction|complete induction]].

For <math>n=1,2</math> we have <math>1\#=1<4</math> and <math>2\#=2<4^2=16</math>.

Let us assume that the inequality holds for all <math>1\le n\le2k-1</math>. Since <math>n=2k>2</math> is composite, we have
:<math>(2k)\#=(2k-1)\#<4^{2k-1}<4^{2k}.</math>

Now let us assume that the inequality holds for all <math>1\le n\le2k</math>. Since <math>\binom{2k+1}{k}=\frac{(2k+1)!}{k!(k+1)!}</math> is an integer and all the primes <math>k+2\le p\le2k+1</math> appear only in the numerator, we have
:<math>\frac{(2k+1)\#}{(k+1)\#}\le\binom{2k+1}{k}=\frac12\!\left[\binom{2k+1}{k}+\binom{2k+1}{k+1}\right]<\frac12(1+1)^{2k+1}=4^k .</math>
Therefore,
:<math>(2k+1)\#=(k+1)\#\cdot\frac{(2k+1)\#}{(k+1)\#}\le4^{k+1}\binom{2k+1}{k}<4^{k+1}\cdot4^k=4^{2k+1}.</math>