Question

Where Pn denotes the n-th prime in ascending order, use induction to prove Pn <= 2 ^ ( 2^ ( n )-1 ). @-------College Al…

Answer 1

this looks tough

Answer 2

Pn \[\le 2 ^{2^{n}-1}\]

Answer 3

base case: P(1) ≤ 2

is the first prime smaller than or equal to 2? yes.

induction hypothesis: P(k) ≤ 2^(2^k - 1)

now we must prove that P(k+1) ≤ 2^(2^(k+1) - 1)

Answer 4

ok

Answer 5

we can start with the expression 2^(2^(k+1) - 1)

= [2^(2^k - 1)]^2 * 2

= 2a^2, where a = 2^(2^k - 1)

we know that a ≥ P(k)

hence 2a^2 is most definitely ≥ P(k)

but since you've taken a number, squared it, and multiplied it by 2, it's definitely going to be bigger than the next prime, too

hence 2a^2 ≥ P(k+1)

hence 2^(2^(k+1) - 1) ≥ P(k+1)

Answer 6

hmm, i think the reasoning in my 6th line is a little iffy.

Answer 7

all the same, i've got a much clearer idea of how to approach this question now. Thank you! :)