Results 1 to 2 of 2

Math Help - Modification of proof of Euclids Theorem

  1. #1
    Junior Member
    Joined
    Aug 2007
    Posts
    32

    Modification of proof of Euclids Theorem

    hi guys i hav no idea where to start on this question.. could you please give me a rough outline on what i should be doing so that i can attempt this question? thanks

    prove that if p_n is the n-th prime then p_n < 2^{2^{n}}.
    hint: use induction on n and try to modify the proof of Euclid's theorem..
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Quote Originally Posted by smoothman View Post
    hi guys i hav no idea where to start on this question.. could you please give me a rough outline on what i should be doing so that i can attempt this question? thanks

    prove that if p_n is the n-th prime then p_n < 2^{2^{n}}.
    hint: use induction on n and try to modify the proof of Euclid's theorem..
    By induction say p_n \leq 2^n.

    Then,
    p_{n+1} \leq p_1\cdot ... \cdot p_n + 1 \leq 2^{2^1}\cdot 2^{2^2}\cdot ... \cdot 2^{2^n} + 1 \leq 2^{2^1+...+2^n} + 1

    That is the key step. See if you can complete my argument. (Hint: Use the geometric series formula).
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: October 8th 2010, 08:55 AM
  2. [SOLVED] Euclids algorithm & congruence equations help
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: June 17th 2010, 11:10 PM

Search Tags


/mathhelpforum @mathhelpforum