13
$\begingroup$

I feel like there must exist a combinatoric proof of a theorem like: There is a prime between $n$ and $2n$, or $p$ and $p^2$ or anything similar to this stronger than there is a prime between $p$ and $(\prod_p p) + 1$ (Euclid's theorem).

I was trying to prove one by the Sieve on this grid

    1     2     3     4 ... p   p+1   p+2   p+3   p+4 ... 2p  2p+1  2p+2  2p+3  2p+4 ... 3p ........................... ........................... ........................... p^2 p^2+1 p^2+2 p^2+3 p^2+4 ... 

but it did not work.

Do any good arguments like this exist? I don't expect anything as strong as Prime Number Theorem or even Bertrand, but surely a direct combination proof can prove that there are lots of primes?

  • 5
    I'm not sure exactly what counts as a combinatorial argument, but it's certainly a phrase I associate with the work of Erdos. So I will note that Erdos, at a very young age, gave a new proof of Bertrand's Postulate. You might want to check that out and see if it is "combinatorial enough" for your purposes or tastes.2011-05-13
  • 2
    To add a reference to @Pete's comment: An extremely nice exposition of Erdős's argument can be found in Aigner and Ziegler's book *Proofs from THE BOOK* (which I heartily recommend to anyone liking beautiful and outstandingly clever mathematics, which is in addition written and exposed with great care for details). The title refers to a phrase of PE about which you can find out on his [Wikipedia page](http://en.wikipedia.org/wiki/Paul_Erdős) in case you're interested.2011-05-13
  • 3
    Chebyshev said/And I say it again/There's always a prime/Between $n$ and $2n$.2011-05-14

3 Answers 3