The content is taken primarily from an excellent Wikipedia article.

Lemma 1:

If n is greater than 5, then 2n/3 is greater than √2n

Proof:

(1) For n ≥ 5, 2n(2n-9) is greater than 0 since 2n ≥ 10 and 2n-9 ≥ 1.

(2) 2n(2n - 9) = 4n

^{2}- 18n.

(3) Since 4n

^{2}- 18n is greater than 0, 4n

^{2}is greater than 18n.

(4) Dividing both sides by 9 gives us 4n

^{2}/9 is greater than 2n.

(5) Taking the square root of both sides gives us 2n/3 is greater than √2n

QED

Lemma 2:

Let p be a prime number that is greater than √2n

Let x be the highest nonnegative integer such that p

^{x}divides 2n!/[(n!)(n!)]

then:

Proof:

(1) We know that in general, the maximum power of p that divides n! is (see Theorem, here):

(2) So the highest power of p that divides (2n)!/[(n!)(n!)] is:

(3) Since p is greater than √2n, it follows that p

^{2}is greater than 2n. So we only need to consider the case where i=1.

(4) This leaves us with:

QED

Lemma 3:

Bertrand's Posulate is true for n less than 2048

Proof:

Between any n less than 2048 and its double, one will find one of the following primes:

3, 5, 7, 13, 23, 43, 83, 163, 317, 631, 1259 and 2503

since:

n = 2 --> 3

n between 3 and 4 --> 5

n between 5 and 6 --> 7

n between 7 and 12 --> 13

n between 13 and 22 --> 23

n between 23 and 42 --> 43

n between 43 and 82 --> 83

n between 83 and 162 --> 163

n between 163 and 316 --> 317

n between 317 and 630 --> 631

n between 631 and 1258 --> 1259

n between 1259 and 2047 --> 2503

QED

Definition 1: R(p,n): maximum divisor of 2n!/(n!)(n!)

Let R(p,n) be the function that returns the maximum power of a given prime that divides 2n!/(n!)(n!)

For any prime p, p

^{R(p,n)}divides 2n!/(n!)(n!) but p

^{R(p,n)+1}does not.

Example 1: R(3,5)

(2*5)!/(5!)(5!) = 10*9*8*7*6/5*4*3*2 = 2*9*2*7*2*2 = 2

^{4}*3

^{2}*7.

R(3,5) = 2 since 3

^{2}divides 2

^{4}*3

^{2}*7 but 3

^{3}= 27 does not.

Lemma 4:

For all p, R(p,n) ≤ 2n

Proof:

(1) The multiplicity m of p in a factorial n! (see Theorem 1, here) is:

so that p

^{m}divides n! but p

^{m+1}does not.

(2) Based on this, the formula for R(p,n) is:

which is equivalent to:

(3) We can see that if p

^{i}is greater than 2n, then:

floor(2n/p

^{i}) = 0 and floor(n/p

^{i}) = 0 so that we have:

floor(2n/p

^{i}) - 2*(n/p

^{i}) = 0

so that we have:

(4) Using the Division Algorithm (see Theorem 1, here), there exists q,r such that:

n = qp

^{i}+ r

where r is less than p

^{i}

(5) From this, we can see that:

since:

Case 1: r = 0

In this case, floor(2n/p

^{i}) = 2q and 2*floor(n/p

^{i}) = 2*q so that:

floor(2n/p

^{i}) - 2*floor(2n/p

^{i}) = 0

Case 2: r is less than (1/2)p

^{i}

In this case, floor(2n/p

^{i}) = 2q and 2*floor(n/p

^{i}) = 2*q so that:

floor(2n/p

^{i}) - 2*floor(2n/p

^{i}) = 0

Case 3: r ≥ (1/2)p

^{i}

In this case, floor(2n/p

^{i}) = 2q+1 and 2*floor(n/p

^{i}) = 2*q so that:

floor(2n/p

^{i}) - 2*floor(2n/p

^{i}) = 1

(5) So that we have:

p

^{i}≤ p

^{logp(2n)}= 2n.

QED

Lemma 5:

For all i:

0 ≤ i ≤ 2n → (2n!)/(n!)(n!) ≥ (2n!)/(i!)(2n-i)!

Proof:

(1) We know that (see Definition 3, here for review of C(n,r) if needed):

C(2n,i-1) = (2n!)/(i-1)!(2n-i+1)!

C(2n,i) = (2n!)/(i!)(2n-i)!

(2) So, we see that:

C(2n,i) = (2n-i+1)/(i)*C(2n,i-1)

and

C(2n,i-1) = (i)/(2n-i+1)*C(2n,i)

(3) If i ≤ n, it follows that:

2n - i + 1 is greater than i since 2n - i + 1 ≥ n+1

So up to i=n, C(2n,i) is greater than C(2n,i-1)

(5) If i ≥ n+1, it follows that:

i is greater than 2n - i + 1 since 2n - i + 1 ≤ n

So down to i=n+1, C(2n,i-1) is greater than C(2n,i)

(6) So, we have shown that C(2n,n) is greater than C(2n,i) for i less than n and C(2n,n) is greater than C(2n,i) for i greater than n.

QED

Corollary 5.1:

Proof:

(1) Using the Binomial Theorem (see Theorem, here):

(2) Using Lemma 5 above, we know that:

(3) So that we have:

(4) And dividing both sides by (2n+1) finishes the proof.

QED

Lemma 6:

If 2

^{t}is less than 8t, then t is less than 6

Proof:

(1) If t=6, then 2

^{t}is greater than 8t since:

2

^{6}= 64

8(6) = 48

(2) Assume it is true up to some t ≥ 6 so that: 2

^{t}is greater than 8t.

(3) Then 2*(2

^{t})=2

^{t+1}is greater than 2*8t = 16t

(4) 16t is greater than 8t+8 since 16=8t + 8t and for t ≥ 6, 8t is greater than 8.

(5) So that we have 2

^{t+1}is greater than 8t+8 = 8(t+1).

QED

Lemma 7:

If:

Then:

n is less than 2048.

Proof:

(1) Let n = 2

^{2t-1}

(2) So 2n = 2

^{2t}

(3) √2

^{2t}= 2

^{t}

(4) So √2nln(2) = 2

^{t}ln(2)

(5) (4)ln(2n) = 4ln(2

^{2t}) = 2t*4*ln(2)

(6) Dividing both sides by ln(2) gives us:

2

^{t}is less than 8t

(7) Using Lemma 6 above, we conclude that t is less than 6.

(8) So, it follows that n is less than 2

^{2(6)-1}= 2

^{11}= 2048.

QED

Theorem: Bertrand's Postulate

For any n, there exists a prime p such that p is greater than n and less than 2n.

Proof:

(1) We know that Bertrand's Postulate is true for n less than 2048 [see Lemma 3 above]

(2) Assume for some n ≥ 2048, there is no prime between n and 2n.

(3) Let p be the largest prime factor of (2n!)/[(n!)(n!)] that is less than or equal to n.

(4) Using Lemma 1 above, we know that p ≤ 2n/3 since:

(a) Assume that that p is greater than 2n/3.

(b) Since n ≥ 2048, using Lemma 1 above, p is also greater than √2n

(c) This means that the highest power of x is given by (see Lemma 2 above):

(d) Since 2n/3 is less than p, it follows that 2n is less than 3p, and further that 2n/p is less than 3 so that 2n/p ≤ 2.

(e) But from step #3 above, we know that n ≥ p so that we have n/p ≥ 1.

(f) This gives us that 2n/p ≤ 2 and n/p ≥ 1 so that we have:

x = floor(2n/p) - 2*floor(n/p) ≤ 2 - 2*1 = 0.

(g) So, under these circumstances, the highest power of x is 0 which means that there is no such p and we can conclude that p ≤ 2n/3.

(5) From step #4, we have:

(2n!)/(n!n!) = ∏ (p ≤ 2n/3) p

^{R(p,n)}

where R(p,n) is a function on p,n such that p

^{R(p,n)}divides (2n!)/(n!n!) but p

^{R(p,n)+1}does not. [see Definition 1 above]

(6) From Lemma 2 above, we know that if p is greater than √2n, then R(p,n)=1 so that we have:

(7) Since there are less than √2n primes less than √2n, using Lemma 4 above, we have:

(8) If we use a limit for primorials (see Theorem, here), we have:

(9) Using Corollary 5.1 above, we also have:

(10) So, putting it all together, we have:

(11) If we multiply 4

^{(-2n/3)}to both sides we get:

(12) Now, since n ≥ 1, we note that 4n

^{2}is greater than 2n+1

(a) For n=1, 4(1)

^{2}is greater than 2(1)+1

(b) Assume that 4n

^{2}is greater than 2n+1

(c) Since n ≥ 1, 4n

^{2}+ 8n is greater than 2n+1+2

(d) 4n

^{2}+ 8n + 1 is greater than 2(n+1) + 1

(e) And:

4(n+1)

^{2}is greater than 2(n+1)+1

(13) So it follows that:

(14) Since n is greater than 18, it follows that (4/3)√2n is greater than 2 + √2n since:

(a) √2(n) is greater than 6

(b) (4/3)√2n = (1/3)√2n + √2n

(c) And (1/3)√2n is greater than (1/3)*6 = 2.

(15) This gives us:

(16) Putting it all together gives us:

(17) Taking the logarithm of both sides, gives us:

(18) We can simplify this further by multiplying 3 to both sides and noting that 4=2

^{2}so that we get:

(19) We can further simplify it by dividing both sides by √2n to get:

(20) But now we use Lemma 7 above to reach a contradiction.

QED

References

- "Proof of Bertrand's Postulate", Wikipedia.org