Does anyone have any good tips on how to think about when I want to show that Pn <2 ^ 2 ^ n and Pn denotes the nth prime number and n = 1,2,3, .. ?

Well, the prime numbers seem to grow at n*ln(n), a much slower rate of growth than the exponential one (Is that 2^(2^n)?).

 

It may help you to know that if you multiply all the prime numbers up to a point and add one, you get a number that is not divisible by any of those prime numbers.

f(n) = 2^(2^n), P(n) = n*log(n)

 

f(0) = 1,.. P(0) = 0 ..(initial condition TRUE)

f(1) = 4,... P(1) = 0

f(2) = 16,... P(2) = 1.4

f(3) = 256,.... P(3) = 3.3

...

f(10) = 309.8, P(10) = 23

 

P(n) is less than f(n) for n <= k, now let's prove it for n = k+1

 

f(k+1) = 2^(2^k+1) = 2^(2^k) * 2^(2^1) = f(k) * 2^2

 

P(k+1) = (k+1) * log(k+1) = k * log(k+1) + log(k+1)

.. = k * log(k+1) + log(k+1) ..(i'll consider log(k+1) = log(k) + epsilon)

... = k * log(k) + epsilon + log(k+1)

.... = P(k) + (epsilon + log(k+1))

 

growth rate of f(k) = f(k) * 2^2 / f(k) * 100 % = 400%

 

growth rate of P(k) = P(k) + epi + log(k+1) / P(k) * 100%

.. = P(k)/P(k) + epi/P(k) + log(k+1)/P(k) * 100%

... = 1 + 0 (canceled) + log(k+1)/k * log(k)

.... = log(k) + epi /k * log(k) = log(k)/k * log(k) + epi/P(k) * 100%

..... = 1/k + 0 * 100%

...... = 1/k * 100% = 100 k^-1 %

 

since, f(K) > P(K)

 

and, growth rate of f(k) >> 100% > growth rate of P(k)

 

then f(K+1) > P(K+1) is TRUE also,