There is a prime between $n$ and $n^2$, without Bertrand Consider the following statement:

For any integer $n>1$ there is a prime number strictly between $n$ and $n^2$.

This problem was given as an (extra) qualification problem for certain workshops (which I unfortunately couldn't attend). There was a requirement to not use Bertrand's postulate (with which the problem is nearly trivial), and I was told that there does exist a moderately short proof of this statement not using Bertrand. This is my question:

How can one prove the above statement without Bertrand postulate or any strong theorems?

Although I can only accept one answer, I would love to see any argument you can come up with.
I would also want to exclude arguments using a proof of Bertrand's postulate, unless it can be significantly simplified to prove weaker statement.
Thank you in advance.
 A: 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.
A: 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.
A: I've come up with a simple proof based on the prime-counting function $\pi(x)$, which I'm pretty sure doesn't depend on Bertrand's Postulate.
First, I will prove a lemma that for every prime $n$, there is another prime $p$ with $n < p < n^2$. I will use this result later to show the general result (i.e. for composite $p$ as well).
Based on some inequalities of $\pi(x)$ and the value of a related constant we have
$$\frac{n}{\log n} < \pi(n) < C\frac{n}{\log n}\text{, where }C=\pi(30)\frac{\log 113}{113} \approx 1.255$$
for all $n \geq 17$. We want to prove that for all prime $n$ we have
$$\pi(n^2) > \pi(n)$$
or
$$\pi(n^2) - \pi(n) > 0,$$
so we look at the upper bound of $\pi(n)$ and the lower bound of $\pi(n^2)$ to find a minimum difference.
We have
$$\begin{align}
\pi(n^2) - \pi(n) &> \frac{n^2}{\log n^2} - C\frac{n}{\log n} \\
&= \left(\frac{n}{2} - C\right)\frac{n}{\log n}
\end{align}
$$
so the conclusion is satisfied whenever
$$\left(\frac{n}{2} - C\right)\frac{n}{\log n} > 0.$$
Since for all prime $n$ we have
$$\frac{n}{\log n} > 0,$$
we find that $\pi(n^2) - \pi(n) > 0$ whenever $\frac{n}{2} - C > 0$, which gives us
$$n > 2C \approx 2.51$$
so $$n \geq 3$$
which is true for every prime $n \geq 17$.
For lesser primes we can prove things manually:
$$2 < 3 < 2^2$$
$$3 < 5 < 3^2$$
$$5 < 7 < 5^2$$
$$7 < 11 < 7^2$$
$$11 < 13 < 11^2$$
$$13 < 17 < 13^2$$
This concludes the lemma.
Then, we must prove that for every composite $n$ there is a prime $p$ with $n < p < n^2$. Take the largest prime less than $n$ and call that $p_m$. Then by applying the lemma we find that there is some prime $p$ such that
$$p_m < p < p_m^2.$$
Because $p > p_m$, $p_m$ is the largest prime less than $n$, and $n$ is composite, we find that 
$$p < n.$$
Also, we have
$$p < p_m^2 < n^2,$$
so we reach the second conclusion: if $n$ is composite then there's a prime $p$ such that
$$n < p < n^2.$$
Now we've proved the original statement for both prime and composite $n$, and the proof is complete.
