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: Primes Proof, Induction

  1. Feb 14, 2010 #1
    I am aiming to prove the following:
    Let 2 = p1 < p2 < p3.... be the sequence of primes in increasing
    order. Prove that pn ≤ 22n-1.(Hint: Show that the method used to prove Euclid’s Theorem also proves that pn ≤ p1p2...pn−1 + 1.)

    So I started doing the proof via induction, letting n=2 be my base case. That's pretty straightforward. I assume that it is true for all n≤k, now I am trying to prove true for k+1.
    My issue lies in the fact I don't know how to tie into the method from Euclid's Thm (pn ≤ p1p2...pn−1 + 1) into what I am actually trying to prove (pn ≤ 22n-1). Any ideas?
  2. jcsd
  3. Feb 14, 2010 #2
    well euclids theorem takes the next prime as p =p1...pn-1 +1. this number is indeed prime distinct from the others. but it might not be the next prime in the increasing sequence of primes. thus, pn must be less than or equal to this value.

    now we have a recurrence relation if we use that inequality. with some effort you can show that pn <= p1(((...(p1+1)((p1+1)+1)+1)))) a nested form. now the highest power that 2 will achieve in this multiplication is equal to 3*2^n-3 since for each n the highest power of two when we multiply the above nested form out is
    3*2^n-3 < 4*2^n-2 -1=2^n-1 -1. then pn <= sum(n=0:2^n-1 -1)=2^2^(n-1)
  4. Feb 14, 2010 #3
    sorry the last inequality is pn <= sum(n=0:2^n-1 -1)=2^2^(n-1) -1 < 2^2^(n-1). also note this strict inequality holds for all n>=2. for n=1 we have equality.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook