18
$\begingroup$

This question already has an answer here:

Let $p_n$ be the n-th prime number, e.g. $p_1=2,p_2=3,p_3=5$. How do I show that for all $n>1$, $p_n<n^2$?

$\endgroup$

marked as duplicate by rtybase, Claude Leibovici, user91500, Namaste, kingW3 Jun 14 '17 at 13:30

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 3
    $\begingroup$ By the PNT, $p_n \sim n \log n$, so it's certainly true asymptotically. Once you figure out where the asymptotics kick in (which requires knowing an explicit error bound, with constants, on that approximation) it remains to check finitely many cases (if it's true). $\endgroup$ – Qiaochu Yuan Jan 6 '15 at 0:38
  • $\begingroup$ Is the asymptotics effective? $\endgroup$ – Bernard Jan 6 '15 at 0:39
  • 2
    $\begingroup$ $p_n \lt n(\log_e n + \log_e \log_e n)$ for $n \ge 6$. More at ams.org/journals/mcom/1999-68-225/S0025-5718-99-01037-6/… $\endgroup$ – Henry Jan 6 '15 at 0:41
  • $\begingroup$ Certainly appears to be true with $n^2-p_n$ strictly increasing. See first 10000 here js.do/caffeinatedlogic/pnn2 $\endgroup$ – David Peterson Jan 6 '15 at 0:49
11
$\begingroup$

In Zagier's the first 50 million prime numbers a very elementary proof is given that for $n > 200$ we have

$$\pi(n) \ge \frac23 \frac{n}{\log n}$$

where $\pi(x)$ is the number of primes below $x$ (as well as a bound in the other direction). In fact, it already holds for $n \ge 3$, as can be directly checked.

Suppose that $p_n > n^2$, then for this $n$ we have $\pi(n^2) < n$, but that violates the bound already for $n = 5$.

$\endgroup$
-1
$\begingroup$

You may use Bertrand's Postulate, which states that, for any natural number $n>1$, there exists a prime number $p$ such that $n<p<2n$; and induction.

First note that the result does not hold for $p_1=2$. However it does hold that $p_2=3<2^2=4$.

Now following an induction argument let's assume that for some fixed $n>1$ it holds that $p_n < 2^n$. Then by Bertrand's Postulate clearly $p_n < p_{n+1} < 2p_n$. So $p_{n+1}<2p_n < 2^{n+1}$.

$\endgroup$
  • $\begingroup$ The question is $p_n < n^2$ not $p_n < 2^n$. $\endgroup$ – Confuse Mar 18 '18 at 10:02
  • 1
    $\begingroup$ I guess I got @Confuse d. Should I delete this answer? $\endgroup$ – Anguepa Mar 19 '18 at 11:40

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