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$?

  • 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 P Jan 6 '15 at 0:49

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


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}$.

  • 1
    $\begingroup$ The question is $p_n < n^2$ not $p_n < 2^n$. $\endgroup$ – Confuse Mar 18 '18 at 10:02
  • 2
    $\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.