Prime Numbers between N and 1+N!

Date: 04/25/2003 at 23:46:31
From: John
Subject: Prime numbers between n and 1 + N!

I've been trying to find a proof of the fact that for each natural
number N, there exists a prime number Q such that N is less than or
equal to Q and Q is less than or equal to 1 + N!

Date: 04/26/2003 at 09:31:21
From: Doctor Paul
Subject: Re: Prime numbers between n and 1 + N!

Let f(x) = 2*x and g(x) = x! + 1 and let N = 1.

f(N) = 2
g(N) = 2

So Q = 2 is the only choice.

Now let N = 2.  Then f(N) = 4 and g(N) = 3.

Clearly, there is no prime Q such that 4 <= Q <= 3.

So the condition isn't true for N = 2.

Now let N = 3.  Then f(N) = 6 and g(N) = 7 and we have Q = 7.

If N = 4, we have f(N) = 8, g(N) = 25, and we have many choices for Q.

The key to this problem is to show that for N >= 3 we have 
f(N) < g (N).  Then we can apply Bertrand's Postulate, which 
guarantees the existence of a prime between n and 2*n for all natural 
numbers n > 1.

There is more about that in Eric Weisstein's World of Mathematics:

   Bertrand's Postulate
   http://mathworld.wolfram.com/BertrandsPostulate.html 

To prove that 2*n < n! + 1 for n >=3, use induction.

It is easily shown to be true for n = 3 since 6 < 7.

Now suppose that 2*n < n! + 1 and consider

2*(n+1) = 2*n + 2 < n! + 3 < n! + 1 < n!*(n+1) +1 = (n+1)! + 1.

Thus we have 2*(n+1) < (n+1)! + 1 and so by the principle of 
mathematical induction, we know that 2*n < n! + 1 for n >=3.

Now apply Bertrand's Postulate and you're finished.

I hope this helps.  Please write back if you'd like to talk about 
this some more.

- Doctor Paul, The Math Forum
  http://mathforum.org/dr.math/