Proving that there are at least $n$ primes between $n$ and $n^2$ for $n \ge 6$ I was thinking about Paul Erdos's proof for Bertrand's Postulate and I wondered if the basic argument could be used to show that there are more than $n$ primes between $n$ and $n^2$.
Is this approach valid?  Is there a better approach?
Here's the argument:


*

*Let $v_p(n)$ be the maximum power of $p$ that divides $n$.


*Using Legendre's Theorem, I calculate that $v_p\left(\dfrac{(n^2)!}{(n!)^n}\right) \le (n-1)n^2$.


*

*Let $n = qp^i + r$ where $0 \le r < p^i$


*For $r < \dfrac{p^i}{n}$, $\left(\left\lfloor\dfrac{n^2}{p^i}\right\rfloor - n\cdot\left\lfloor\dfrac{n}{p^i}\right\rfloor\right) = 0$


*For $r \ge \dfrac{p^i}{n}$, $\left(\left\lfloor\dfrac{n^2}{p^i}\right\rfloor - n\cdot\left\lfloor\dfrac{n}{p^i}\right\rfloor\right) \le n-1$


*For $p^i > n^2$,  $\left(\left\lfloor\dfrac{n^2}{p^i}\right\rfloor - n\cdot\left\lfloor\dfrac{n}{p^i}\right\rfloor\right) = 0$




*Using the multinomial theorem I get:  $\dfrac{n^{n^2}}{n^2+1} < \dfrac{(n^2)!}{(n!)^n}$.

*

*$n^{n^2}=(1 + 1  + \cdots + 1)^{n^2}
 = \sum\limits_{k_1+k_2+\cdots+k_n=n^2} {n^2 \choose k_1, k_2, \ldots, k_n}
  \prod\limits_{1\le t\le n^2}x_{t}^{k_{t}}\,,$ where ${n^2 \choose k_1, k_2, \ldots, k_n}
 = \frac{(n^2)!}{k_1!\, k_2! \cdots k_n!}$


*$n^{n^2} < (n^2+1)\left(\dfrac{(n^2)!}{(n!)^n}\right)$


*$\dfrac{n^{n^2}}{n^2+1} < \dfrac{(n^2)!}{(n!)^n}$




*$\dfrac{(n^2)!}{(n!)^n} <  [(n-1)(n^2)]^n\prod\limits_{n < p \le n^2} n$


*$\dfrac{n^{n^2}}{n^2+1} <  [(n-1)(n^2)]^n\prod\limits_{n < p \le n^2} n$


*For $n \ge 1, \dfrac{n^{n^2}}{n^{4n}} < \dfrac{n^{n^2}}{(n^2+1)[(n-1)(n^2)]^n} <  \prod\limits_{n < p \le n^2} p$


*For $n \ge 6$, $n^2 - 4n = n(n-2) \ge 2n$


*$(2\log n)(\pi(n^2) - \pi(n)) > \sum\limits_{n < p \le n^2} \log p > (n^2-4n)\log n > (2n)\log n$


*So $\pi(n^2) - \pi(n) > n$.


Thanks,
-Larry

Edit: I believe that step 4 is not correct.  If I can save the argument, I will update it.  Otherwise, please check out the link in the answer.

We have the following result1:

(Chebyshev, 1850) For any $X>30$, we have: $$\pi(X)\cdot\frac{\log
 X}{X} \in (A,B),$$ where
   $A=\log\left(\frac{2^{\frac{1}{2}}3^{\frac{1}{3}}4^{\frac{1}{4}}}{30^{\frac{1}{30}}}\right)\approx
 0.946$ and $B=\frac{6}{5}A\approx 1.135$.

It follows that for any $X>30$ we have:
$$ \pi(X^2)-\pi(X)\geq A\frac{X^2}{2\log X}-B\frac{X}{\log X}\geq\left(\frac{A}{2}-\frac{B}{30}\right)\frac{X^2}{\log X}\geq\color{red}{\frac{2}{5}\frac{X^2}{\log X}} $$
that is way greater than $X$. So we just need to check that the our claim holds in the range $[6,30]$.
1) it is a weaker version of the PNT, but not so weaker. Its proof only relies on the properties of the central binomial coefficients, and it is rather short and ingenious.
