Proof of Prime ? HELP!

[Koya]

Here's a challange for everyone.

This is an algebra question:

Let Pn be the nth positive prime in the usual ordering. Use induction to prove that Pn <= 2^2^(n-1).

(Hint: Use proof of infinetly many primes)

Please help anyway you can.

[jemidiah]

Can you give us the proof of infinitely many primes?

[Koya]

Sure, here it is:

Suppose that there exist only finitely many primes p1 < p2 < ... < pr. Let N = (p1)(p2)...(pr) > 2. The integer N-1, being a product of primes, has a prime divisor pi in common with N; so, pi divides N - (N-1) =1, which is absurd!

(I copied this from http://www.utm.edu/research/primes/n...e/kummers.html).

This is the same proof that my prof. used in class.

Hopefully this helps answer the question.

[sql_lall]

I know this isn't really the point but...

Pn <= 2^2^(n-1)

Isn't this an obscenely high Upper bound for the nth prime? Isn't there some Sieve-of-thatgreekguy that could help out with this?

Anyway, the proof itself isn't too hard, just uses strong induction. as in, assume true for all previous (n-1) primes, then multiply together...

[Koya]

sorry, still confused.

How does the Sieve-of-Eratosthenes help with this? From what I know, it is used to find all primes <= to n (where n is any number).

When you say multiply together, could you be more specific?

Thanks for all your help.

[TheManWhoCan]

Well here goes, I'm ad-libbing this:

First, see if it's true for n = 1:

LHS = 2
RHS = 2 <= LHS so yeah it holds for n = 1.

Now suppose it's true for n = k (where k is a positive integer), i.e. that P_k <= 2^2^(k-1).

Square both sides (no problems there because both sides are always positive):

P_k² <= 2^2^k

At which point I don't know what to do. Usually you play with that until you end up with:

P_k+1 <= 2^2^k

Upon which you shout "hazaar" three times and leave the room, but I can't immediately see how to continue and it's getting late.

[bugzpodder]

apply bertrand's postulate