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

Primorial

The primorial is the product of primes less than or equal to a number n.

Definition: Primorial: n#

The primorial n# is defined as follows:



Example:

1# = 1

3# = 3*(2#) = 3*2*(1#)=3*2

6# = 5# = 5*3*2


Theorem: if n≥ 1, then n# is less than 4ⁿ

Proof:

(1) It is true for (n=1 and n=2)

For n=1, 1#=1 is less than 4.

For n=2, 2#=2 is less than 4² = 16

(2) If n is even and n is greater than 2, then n is composite and we have:

n# = (n-1)# which is proven if we show that (n-1)# is less than 4^n-1 since 4^n-1 is less than 4ⁿ.

(3) To complete the proof, we show that n# is less than 4ⁿ if n is odd:

(a) By the inductive hypothesis, we can assume that it is true for all integers less than n and we assume that n is an odd integer where n=2x+1 and x ≥ 1 so that n ≥ 3.

(b) Now, we note that 4^m = (1+1)^2m = (2^-1)*(1+1)^2m+1 = (1/2)(1+1)^2m+1

(c) Using the Binomial Theorem (see here), we note that:

(1+1)^2m+1 = ∑ (i=0, 2m+1) (2m+1!)/[(i!)(2m+1-i)!]

(d) So,

(1/2)(1+1)^2m+1 = (1/2) ∑ (i=0, 2m+1) (2m+1)!/[(i!)(2m+1-i)!]

is greater than:

(1/2) [(2m+1)!/(m!)(m+1)! + (2m+1)!/(m+1)!(m)!] = (2m+1)!/(m!)(m+1)!

(e) So, from (b) and (d), we can conclude that:

4^m is greater than (2m+1)!/(m!)(m+1)!

since 4^m = (1/2)(1+1)^2m+1 which is greater than (2m+1)!/(m!)(m+1)!

(f) Each prime p that is greater than m+1 and less than 2m+1 divides (2m+1)!/(m+1)!(m!) since:

(2m+1)!/(m+1)!(m!) is an integer. [see Lemma 5, here]

Let u = (2m+1)!/(m+1)!(m!)

(2m+1)! = u(m+1)!(m!)

Since p does not divide (m+1)! and does not divide (m!), by Euclid's Generalized Lemma (see Corollary 2.1, here), p must divide u.

(g) This gives us:




From the definition of primorial [see Definition above], step #3f above, and step #3e above.

(h) From the inductive hypothesis in step #3a, we can assume that:

(m+1)# is less than 4^m+1

(i) So, we have (using step #3g above):

n# = (2m+1)# which is less (m+1)#*4^m

(j) Using step #3h above, we have:

(2m+1)# is less than 4^m+1*4^m = 4^2m+1

QED

References

• "Primorial", Wikipedia.org
• "Proof of Bertrand's Postulate", Wikipedia.org
  

Pascal's Rule

Theorem: Pascal's Rule

C(n,k) + C(n,k-1) = C(n+1,k)

where:



Proof:

(1) We can find a common denominator for C(n,k) and C(n,k-1) so that we have:





(2) So that:






(3) To complete the proof, we note that: n-k+1 = n+1-k so that we have:



= C(n,k+1)

QED

References

• "Pascal's Rule", Wikipedia.org
  

Multiplicity of a Prime Factor

Definition 1: Multiplicity of a prime factor

The multiplicity of a prime factor of a given integer is the highest power of that factor that divides the integer.

Example 1: 60

The prime factorization of is 2*2*3*5

The multiplicity of 3 is 1. The multiplicity of 5 is 1. The multiplicity of 2 is 2.

Adrien-Marie Legendre came up with the following theorem regarding the multiplicity of a prime for n!. (For review of factorials (n!), see here)

Theorem 1: The multiplicity of a given prime p in n! is:



That is, let x = the multiplicity of a prime p.

Then p^x divides n! but p^x+1 does not.

Proof:

(1) If p is greater than n, then p doesn't divide n! and the answer is 0.

(2) So, we can assume p ≤ n.

(3) Let k be the largest power of p such that p^k ≤ n.

(4) For each 1 ≤ i ≤ k, the number of integers from 1 to n that are divisible by pⁱ but not divisible by pⁱ⁺¹ is:



If no numbers are divisible by pⁱ, then floor(n/pⁱ) = 0 [as does floor(n/pⁱ⁺¹)].

floor(n/pⁱ⁺¹) equals the number of integers that are greater than pⁱ⁺¹ and divisible by pⁱ⁺¹.

So the number of integers that are uniquely divisible by pⁱ is the difference of these two floor functions.

(5) The value of p^x which divides n! is equal to the product of all the powers of p that divide any of the integers in the sequence from 1 .. n.

(6) So, the we can compute the value of x with:



(7) Putting this together, we see the following pattern:



(8) We can see for i=1, we have floor(n/p¹), for i=2, we have 2*floor(n/p²) - 1*floor(n/p²), and for i=3, we have 3*floor(n/p³) - 2*floor(n/p³) and so on.

(9) The net result of this is that we rewrite the equation in step #7 to the following:



QED

References:

• "Prime Power Dividing a Factorial", PlanetMath.Org
• "Multiplicity", Wikipedia.Org