Bertrand's postulate states that for any integer $n>3$, there's always a prime $p$ between $n$ and $2n-2$. That result sets a reasonable 'lower bound' on how often we can expect primes to show up, and there are even better estimates (such as the Prime Number Theorem, although that one is an asymptote, and doesn't prove any result for a specific $n$).
However, the proofs of the results above aren't obvious; I'm looking for elementary claims, ones that follow straight from the definition of a prime number (and perhaps some algebraic manipulation).
For example, the following can be deduced using Euclid's method for the infinitude of primes:
Claim: Let $M_n$ Denote the product of all primes smaller than or equal to $n$. Then, if $n \geq 2$, there's at least one prime $p$ such that $n<p\leq M_n+1$.
Proof: If $M_n+1$ is prime, we're done.
Otherwise, $M_n+1$ is divisible by a smaller prime $p$. Then $p$ can't divide $M_n$. but $M_n$ is divisible by all numbers smaller than or equal to $n$, so we get $n<p<M_n+1$, just as we wanted. $\square$
In particular, this shows that there's always a prime number between $n$ and $n!$.
Now, how can we lower this bound? Is there any elementary proof for how there's always a prime between $n$ and $n^2$? What about, say, $n$ and $1000^n$?