2
$\begingroup$

Prove that the nth prime number $p_n$ (with $p_1 = 2, p_2 = 3, p_3 = 5$, etc.) satisfies $p_n \leq 2^{2n-1}$

So far I have figured out that $p_n$ = the nth prime and that I have to use mathematical induction to prove $p_n \leq 2^{2n-1}$. This is similar to the proof of infinitely many primes such that
$m = 1 + p_1 p_2 p_3\cdots p_n$ so there exists a prime $p | m$.

With this information I have concluded that $p_{n+1} \leq p \leq m = 1 + p_1 p_2 p_3\cdots p_n$

I need to figure out how to produce the right side of this inequality with induction. I'm not sure how to do this.

Thank you for any and all help.

$\endgroup$
  • 1
    $\begingroup$ Good so far. What can you say about that product? Use the induction hypothesis. $\endgroup$ – saulspatz Feb 15 '18 at 4:17
  • 1
    $\begingroup$ For induction purposes, if you can show that $p_{k+1}\le 4p_k$, you are good. Not saying that is easy, but that is the induction frame. you need to meet. $\endgroup$ – Joffan Feb 15 '18 at 4:17
  • 1
    $\begingroup$ Your bound would have to be a lot better than $1+p_1p_2p_3\ldots p_n$ for this to work. $\endgroup$ – Robert Israel Feb 15 '18 at 4:57
1
$\begingroup$

A theorem(I forgot its name) states that there is always a prime between $n$ and $2n$.

Let’s jump to the inductive step.

Assume $$p_n \le 2^{2n-1}$$ is true.

Since there is a prime between $p_n$ and $2p_n$, $p_{n+1}<2p_n$.

So, $$p_{n+1}<2*2^{2n-1}<2^{2n}<2^{2(n+1)-1}$$

Therefore, $P(n+1)$ is true when $P(n)$ is true.

The base case is $n=1$, $p_1=2$.

By the principle of mathematical induction, the statement is true.

$\endgroup$
  • 1
    $\begingroup$ I guess OP is asking for a proof from scratch in which case, using a Bertrand's Postulate imply proving the theorem first. $\endgroup$ – Nilos Feb 15 '18 at 8:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.