I once found the following problem meant to be solved at high-school level (some olympiad-level exercise, I guess), and I have never been able to prove it using elementary methods. Does anybody know a solution, please?

Show that if $p_n$ is the $n$-th prime (with $p_1 = 2$) then $p_n \leq \frac {n^2 +3n +4} 4$. In a weaker form, show that $p_n = O(n^2)$, but using only elementary methods.

(Later edit: I remembered that the original statement had an "over $4$" denominator, making the inequality tighter.)

  • 1
    $\begingroup$ In order to prove your result by induction if $f(n)=n^2+3n+4$ we have to prove that there is prime between $f(n)$ and $f(n+1)$ which still an unsolved problem in number theory (even for simple functions as $f=x^2$), If we use Bertrand's postulate we can conclude that $p_n\leq 2^n$ which is not what we need to prove, so I think that it would be very interesting if there is a solution at a high-school level $\endgroup$ – Elaqqad Apr 12 '15 at 19:11
  • $\begingroup$ An extremely minor point: $n^2 + 3n + 4$ is always even, and $p_1 = 2 < 8$, so the inequality can be strict. $\endgroup$ – Robert Soupe Apr 12 '15 at 19:27
  • $\begingroup$ Ah, okay, with that edit, the question becomes much more difficult (and now the question as first posed seems quite easy). $\endgroup$ – Robert Soupe Apr 12 '15 at 20:15
  • 1
    $\begingroup$ See my answer to a similar question: math.stackexchange.com/a/1092552/9911. This only has to be changed very slightly, to conclude that $\pi({n^2 + 3n + 4\over4}) > n$. $\endgroup$ – doetoe Apr 12 '15 at 20:19
  • $\begingroup$ @doetoe: I'm not trained in arithmetic; could you elaborate a little bit more on what to do next with $\pi (n)$, please? I don't know how to link it to my problem. Thank you. $\endgroup$ – Alex M. Apr 12 '15 at 20:22

See my answer to a similar question: it can be proved by elementary means (as in Zagier's beautiful "The first 50 million prime numbers") that for $n \ge 3$

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

where $\pi(x)$ is the number of primes below $x$. The statement that $p_n \leq \frac {n^2 +3n +4} 4$ is equivalent to $\pi\left(\frac {n^2 +3n +4} 4\right) \ge n$. For $n = 1,2$ this can be checked directly, for $n\ge3$ it follows from the above inequality.


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.