Bertrand's Postulate (Theorem)

In today's blog, I will present a proof for Bertrand's Postulate which is really a theorem.

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² - 18n.

(3) Since 4n² - 18n is greater than 0, 4n² is greater than 18n.

(4) Dividing both sides by 9 gives us 4n²/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² 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⁴*3²*7.

R(3,5) = 2 since 3² divides 2⁴*3²*7 but 3³ = 27 does not.


Lemma 4:

For all p, 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ⁱ is greater than 2n, then:

floor(2n/pⁱ) = 0 and floor(n/pⁱ) = 0 so that we have:

floor(2n/pⁱ) - 2*(n/pⁱ) = 0

so that we have:



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

n = qpⁱ + r

where r is less than pⁱ

(5) From this, we can see that:



since:

Case 1: r = 0

In this case, floor(2n/pⁱ) = 2q and 2*floor(n/pⁱ) = 2*q so that:

floor(2n/pⁱ) - 2*floor(2n/pⁱ) = 0

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

In this case, floor(2n/pⁱ) = 2q and 2*floor(n/pⁱ) = 2*q so that:

floor(2n/pⁱ) - 2*floor(2n/pⁱ) = 0

Case 3: r ≥ (1/2)pⁱ

In this case, floor(2n/pⁱ) = 2q+1 and 2*floor(n/pⁱ) = 2*q so that:

floor(2n/pⁱ) - 2*floor(2n/pⁱ) = 1

(5) So that we have:

pⁱ ≤ p^log_p(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⁶ = 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^tln(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¹¹ = 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² is greater than 2n+1

(a) For n=1, 4(1)² is greater than 2(1)+1

(b) Assume that 4n² is greater than 2n+1

(c) Since n ≥ 1, 4n² + 8n is greater than 2n+1+2

(d) 4n² + 8n + 1 is greater than 2(n+1) + 1

(e) And:

4(n+1)² 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² 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