There is a prime between $n$ and $n^2$, without Bertrand

Solution 1:

I have stumbled upon this paper due to Erdős, which in the course of proving something far more general proves this result (see a remark at the end of this page). I am replicating that proof here, with minor modifications by myself.

Suppose $n>8$ and that there are no primes between $n,n^2$. Since clearly (obvious induction works) $\pi(n)\leq\frac{1}{2}n$, by assumption we have $\pi(n^2)=\pi(n)\leq\frac{1}{2}n$. Now consider number $\binom{n^2}{n}$. All of its prime factors are less than $n^2$, and so less than $n$. We have the following inequality:

$$\binom{n^2}{n}=\frac{n^2}{n}\frac{n^2-1}{n-1}\dots\frac{n^2-n+2}{2}\frac{n^2-n+1}{1}>\frac{n^2}{n}\frac{n^2}{n}\dots\frac{n^2}{n}\frac{n^2}{n}=\left(\frac{n^2}{n}\right)^n=n^n$$

At the same time, consider $p$ prime and let $p^a$ be the greatest power of $p$ less than or equal to $n^2$. Since $\binom{n^2}{n}=\frac{(n^2)!}{(n^2-n)!n!}$, By Legendre's formula, exponent of the greatest power of $p$ dividing this binomial coefficient is equal to

$$\left(\lfloor\frac{n^2}{p}\rfloor-\lfloor\frac{n^2-n}{p}\rfloor-\lfloor\frac{n}{p}\rfloor\right)+\left(\lfloor\frac{n^2}{p^2}\rfloor-\lfloor\frac{n^2-n}{p^2}\rfloor-\lfloor\frac{n}{p^2}\rfloor\right)+\dots+\left(\lfloor\frac{n^2}{p^a}\rfloor-\lfloor\frac{n^2-n}{p^a}\rfloor-\lfloor\frac{n}{p^a}\rfloor\right)\leq 1+1+\dots+1=a$$

(first equality is true, because all further terms in the sum are zero. First inequality is true because for any $a,b\in\Bbb R$ $\lfloor a+b\rfloor-\lfloor a\rfloor-\lfloor b\rfloor\in\{0,1\}$)

Since $\binom{n^2}{n}$ is a product of at most $\pi(n)$ prime powers, all at most $p^a\leq n^2$ (by above), we must have

$$\binom{n^2}{n}\leq (n^2)^{\pi(n)}\leq (n^2)^{\frac{1}{2}n}=n^n$$

We have proved two contradictory inequalities, so this ends the proof by contradiction.

Solution 2:

After a little bit of searching on the net, it seems that this result isn't as easy to prove (without Bertrand that is) as one would hope. However, here: https://mathoverflow.net/a/52085, you can find the proof of the result you're looking for. Basically, the author shortens Bertrand's Postulate's proof so that it only proves your desired result.