The proof uses the following four
lemmas to establish facts about the primes present in the central binomial coefficients.
Lemma 1 For any
integer n>0, we have :\frac{4^n}{2n} \le \binom{2n}{n}.
Proof: Applying the
binomial theorem, :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}, since \tbinom{2n}{n} is the largest term in the sum in the left-hand side, and the sum has 2n terms (including the initial 2 outside the summation).
Lemma 2 For a fixed prime p, define R = R(n,p) to be the
p-adic order of \tbinom{2n}{n}, that is, the largest
natural number r such that p^r divides \tbinom{2n}{n}. For any prime p, p^{R }\le 2n.
Proof: The exponent of p in n! is given by
Legendre's formula :\sum_{j = 1}^\infty \left\lfloor \frac{n}{p^j} \right\rfloor\!, so :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) But each term of the last summation must be either zero (if n/p^j \bmod 1) or one (if n/p^j\bmod 1\ge1/2), and all terms with j>\log_p(2n) are zero. Therefore, :R \le \log_p(2n), and :p^R \le p^{\log_p(2n)} = 2n.
Lemma 3 If p is an
odd prime and \frac{2n}{3} , then R(n,p) = 0.
Proof: There are exactly two factors of p in the numerator of the expression \tbinom{2n}{n}=(2n)!/(n!)^2, coming from the two terms p and 2p in (2n)!, and also two factors of p in the denominator from one copy of the term p in each of the two factors of n!. These factors all cancel, leaving no factors of p in \tbinom{2n}{n}. (The bound on p in the preconditions of the lemma ensures that 3p is too large to be a term of the numerator, and the assumption that p is odd is needed to ensure that 2p contributes only one factor of p to the numerator.)
Lemma 4 An upper bound is supplied for the
primorial function, :n\#=\prod_{p\,\le\,n}p, where the product is taken over all
prime numbers p less than or equal to n. For all n\ge1, n\#.
Proof: We use
complete induction. For n=1,2 we have 1\#=1 and 2\#=2. Let us assume that the inequality holds for all 1\le n\le2k-1. Since n=2k>2 is composite, we have :(2k)\#=(2k-1)\# Now let us assume that the inequality holds for all 1\le n\le2k. Since \binom{2k+1}{k}=\frac{(2k+1)!}{k!(k+1)!} is an integer and all the primes k+2\le p\le2k+1 appear only in the numerator, we have :\frac{(2k+1)\#}{(k+1)\#}\le\binom{2k+1}{k}=\frac12\!\left[\binom{2k+1}{k}+\binom{2k+1}{k+1}\right] Therefore, :(2k+1)\#=(k+1)\#\cdot\frac{(2k+1)\#}{(k+1)\#}\le4^{k+1}\binom{2k+1}{k} ==Proof of Bertrand's Postulate==