This question already has an answer here:

Between $n$ and $2n$ there is always a prime number.

I was thinking of this and looked it up on the google to find that this is true. Now, I am wondering what is the proof for it? Does any elementary proof exist for it?

Thank you.


marked as duplicate by Eric Naslund, Daniel Fischer, user133281, user98602, Semiclassical Sep 10 '14 at 21:51

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.

  • $\begingroup$ Yes, it's quite direct. Most basic analytic number theory books will have a proof. DeKonick and Luca have it on p.29, for example. $\endgroup$ – Adam Hughes Sep 3 '14 at 18:04
  • $\begingroup$ There are much tighter bounds for this, like between $n^2$ and $(n+1)^2$. $\endgroup$ – barak manos Sep 3 '14 at 18:05
  • 1
    $\begingroup$ But a proof for these tighter bounds is much more difficult. $\endgroup$ – Peter Sep 3 '14 at 18:06
  • 1
    $\begingroup$ It's not absolutely trivial. It's called Bertrand's postulate, $\endgroup$ – Thomas Andrews Sep 3 '14 at 18:06
  • 3
    $\begingroup$ @barakmanos Between $n^2$ and $(n+1)^2$ [that's Legendre's conjecture, iirc?] is as far as I know still open. If it's proved, that would be very recent. $\endgroup$ – Daniel Fischer Sep 3 '14 at 18:10

Yes, many elementary proofs are known. Apart from the the original proof of Chebyshev's theorem, have a look at the Erdos' elementary proof - you can find it also in Proofs from THE BOOK.

  • $\begingroup$ The latter is a 6-page PDF. It might seem short compared to some other proofs of various theorems I've seen, but it would still take me a couple of hours of careful reading. $\endgroup$ – Mr. Brooks Sep 3 '14 at 21:37
  • $\begingroup$ Life is hard, little my padawan! :D Out of joke, the main idea is pretty straighforward to grasp: any prime between $n$ and $2n$ divide the numerator of $\binom{2n}{n}=\frac{2n(2n-1)\cdot\ldots\cdot(n+1)}{n!}$ but not the denominator, hence we can say something about the distribution of prime numbers by studying how fast the central binomials grow. $\endgroup$ – Jack D'Aurizio Sep 3 '14 at 21:48
  • 2
    $\begingroup$ You're telling me life is hard? That gave me quite a chuckle. Whatever. May you live and prosper as long as I have already. $\endgroup$ – Mr. Brooks Sep 3 '14 at 21:52

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