I am interested in a proof that for all $n \in \mathbb{N}$ (with just a few exceptions) there will always be a prime $p$ such that $\frac{n}{3} \lt p \le \frac{n}{2}$. Note that the exact boundaries are important (i.e. we don't allow $\frac{n}{3}$). This seems to be true for all $n \gt 3$ except $n=9$ and $n=21$. Does anyone know how to prove this? I found this paper, showing that there is always a prime in the interval $[2n,3n]$, I'm not sure if there is a way to use that. I was able to prove easily that there will always be a prime with $\frac{n}{2} \lt p \le n$ for all $n \gt 2$ with Bertrand's Postulate. Any ideas?
EDIT:
I have found a way to prove it, see the accepted answer below.
For anyone who is interested in this intermediate result, I will leave this here:
I can prove the statement for all numbers that are not of the form $6k+3, k \in \mathbb{N}$. For $n=6k$ it follows directly from the paper showing there is always a prime in the interval $[2k,3k]$. Since $2k$ and $3k$ are clearly not prime for $k>1$, we can exclude them as well (in fact, we are already excluding $2k$ in the case $n=6k$). So if we choose $n_1=6k+1$ and $n_2 = 6k+2$ we get that $$]\frac{n_1}{3},\frac{n_1}{2}] \cap \mathbb{N} = ]\frac{n}{3},\frac{n}{2}] \cap \mathbb{N} \subseteq ]\frac{n_2}{3},\frac{n_2}{2}] \cap \mathbb{N},$$
meaning we have at least the same numbers and therefore there is still a prime $p$ with $\frac{n}{3}\lt p \le \frac{n}{2}$. The same is true for $n_{-1}=6k-1$ and $n_{-2}=6k-2$, where the lower bound goes down, so we certainly don't exclude any numbers on that side and the upper bound goes down only enough to exclude $\frac{n}{2}=3k$, which isn't a prime for $k>1$. This argument doesn't work for $n = 6k \pm 3$.
Best Answer
This paper claims to prove that there is a prime in $[3n, 4n]$ for all positive integers $n$. That should suffice for your purposes (for sufficiently large $n$).
Of course you could also take your favourite explicit version of the prime number theorem, but that requires a bit more work.
Edit: Let us complete the argument. Take $n$ sufficiently large (how large we will determine at the end). Now take the smallest integer $k$ so that $3k > \frac n 3$. Note that $3k$ is at most $3$ larger than $\frac n3$. By the theorem I quoted above, there is a prime in $[3k, 4k]$. Since $3k \leq \frac n3 + 3$, we have that $4k \leq \frac 49 n + 4$. Now if we take $n \geq 100$ (say) we have that $\frac 49 n + 3 = \frac 12 n + 3 - \frac{1}{18}n < \frac12 n$. Thus the prime that is in the interval $[3k, 4k]$ is also in the interval $\left(\frac n3, \frac n2\right]$.