A proof

Proof: Let n# be the product of all the primes not exceeding n. We want to show that

(*)       n# < 4^n for n =2, 3, 4, ...

We use induction.

1) n = 2 is trivial.

2) We assume inequality (*) is true for 2, 3, 4,..., (n-2), (n-1).

3) The n case

a) n is even

n# = (n-1)# < 4^(n-1) < 4^n.

b) n is odd

We write n = 2m + 1 and calculate

2 x 4^m = (1 + 1)^(2m+1) = C(n,0) + ... + C(n,n) > C(n,m) + C(n,m+1) = 2 x C(n,m).

So, C(2m+1,m) < 4^m.

Each prime p bigger than (m+1) but not exceeding (2m+1) divides (m+2)(m+3)...(2m+1) and gcd(p, m!) = 1. This implies that p divides C(2m+1,m).

Since [(2m+1)#]/[(m+1)#] is the product of all such p's, we have

[(2m+1)#]/[(m+1)#] < C(2m+1,m) < 4^m.

Therefore,

(2m+1)# < 4^m x [(m+1)#] < 4^m x 4^(m+1) = 4^(2m+1).

By (a) and (b), inequality (*) is also true for n.

By induction, inequality (*) must be true for all n = 2, 3, 4, ...

We have completed the proof.

所有跟帖： 

• 中! -nj_guy- ♂ (1204 bytes) () 11/11/2011 postreply 12:03:03