I am trying to prove there is a prime between $n$ and $n^2+1$ without using Bertrand's postulate or Prime number theorem.
Do you have any idea?
Yuval Filmus's answer for this problem provides a quite useful idea.
But since $n^2+1\lt n!$ for $n\ge4$, I do not know how to use it for this question.
Attempt 1 (failure):
Since $n^2+1$ is an integer, there exists some prime $p\le n^2+1$ such that $p\mid n^2+1$.
Suppose by way of contradiction we have $p<n$ for all $p\mid n^2+1$. Then $p\mid n^2$. But then $p\not\mid n^2+1$, because $n^2+1=kp+1$ for some $k\in\mathbb{N}$.
Thus for some $p\mid n^2+1$ we must have $n\le p\le n^2+1$.
Why does this not work? @Daniel Fischer points out that $n=7$ is a counterexample. All the primes that divide $n^2+1=50=2\cdot 5^2$ are smaller than $7$ and none of them divide $n^2$.