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 4n
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 42 = 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 4n-1 since 4n-1 is less than 4n.
(3) To complete the proof, we show that n# is less than 4n 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 4m = (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:
4m is greater than (2m+1)!/(m!)(m+1)!
since 4m = (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 4m+1
(i) So, we have (using step #3g above):
n# = (2m+1)# which is less (m+1)#*4m
(j) Using step #3h above, we have:
(2m+1)# is less than 4m+1*4m = 42m+1
QED
References
- "Primorial", Wikipedia.org
- "Proof of Bertrand's Postulate", Wikipedia.org
No comments :
Post a Comment