Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Another algebra problem about prime and induction

  1. Sep 21, 2010 #1
    1. The problem statement, all variables and given/known data

    prove by induction that the [itex]n^{\text th}[/itex] prime is less than [itex]2^{2^{\text n}}[/itex]

    2. Relevant equations
    hint:assume it is correct for all [itex]n \leq k[/itex], and then compare [itex]p_{k+1}[/itex] with [itex]p_{1}p_{2}..........p_{k}+1[/itex]

    3. The attempt at a solution
    is [itex]p_{k+1}[/itex] smaller/greater than [itex]p_{1}p_{2}..........p_{k}+1[/itex] so that i can extend the use of inequality?
    I attempt to use euclidean algorithm but do not know where to use.
    Thank you.
  2. jcsd
  3. Sep 21, 2010 #2


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    If [tex]p_{k+1}[/tex] is larger than the suggested number, you should be able to prove that it has no prime divisors which is a contradiction
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook