Thread: Modification of proof of Euclids Theorem

1. 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..

2. Originally Posted by smoothman
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).