A direct proof that there is a prime between $n$ and $n^2+1$?

We need to find (or at least prove the existence of) a positive integer $K = K(n)$ having a prime factor between $n$ and $n^2+1$.

For a prime $p$ and a postivie integer $k$, let $v_p(k)$ denote the exponent of $p$ in the prime factorisation of $k$, i.e. $v_p(k)$ is characterised by $p^{v_p(k)} \mid k$ and $p^{v_p(k)+1} \nmid k$. Next recall Legendre's formula

$$v_p(n!) = \sum_{\ell = 1}^{\infty} \biggl\lfloor \frac{n}{p^{\ell}}\biggr\rfloor = \sum_{\ell = 1}^{\bigl\lfloor \frac{\log n}{\log p}\bigr\rfloor} \biggl\lfloor \frac{n}{p^{\ell}}\biggr\rfloor$$

for the prime factorisation of the factorials. Much of Legendre's formula generalises to arbitrary (increasing) arithmetic progressions. If we have an arithmetic progression

$$A_m = a + m\cdot d$$

with $a \geqslant 0$ and $d > 0$, then for every $r$ coprime to $d$ exactly one of every $r$ consecutive terms of the progression is a multiple of $r$. Let $\mu_r(k)$ denote the number of multiples of $r$ among $A_1, A_2, \dotsc, A_k$. Without any special knowledge about $d$ and $r$ we cannot pin down $\mu_r(k)$ exactly, but we know that for $r$ coprime to $d$ we have

$$\biggl\lfloor \frac{k}{r}\biggr\rfloor \leqslant \mu_r(k) \leqslant \biggl\lceil \frac{k}{r}\biggr\rceil.$$

By the same argument that shows Legendre's formula we can, for the "A-orial"

$$P_k = \prod_{m = 1}^k A_m,$$

see that

$$v_p(P_k) = \sum_{\ell = 1}^{\infty} \mu_{p^{\ell}}(k)$$

for all primes $p$. For primes not dividing $d$, although we cannot give an explicit exact form for $v_p(P_k)$, we have pretty reasonable bounds, namely

$$\sum_{\ell = 1}^{\bigl\lfloor \frac{\log k}{\log p}\bigr\rfloor} \biggl\lfloor \frac{k}{p^{\ell}}\biggr\rfloor \leqslant v_p(P_k) \leqslant \sum_{\ell = 1}^{\bigl\lfloor \frac{\log A_k}{\log p}\bigr\rfloor} \biggl\lceil \frac{k}{p^{\ell}}\biggr\rceil,$$

since evidently $\mu_r(k) = 0$ for $r > A_k$.

Now let's come to the proof that for $n > 1$ there is always a prime strictly between $n$ and $n^2$ (for $n = 1$ we need the extra $+1$). Fix $n \geqslant 2$, and let $p_s$ be the largest prime not exceeding $n$, so $p_s \leqslant n < p_{s+1}$. Consider the arithmetic progression

$$A_m = 1 + m \cdot p_s$$

and let $k = p_s - 1$. On the one hand, we have

$$P_k = \prod_{m = 1}^k A_m > \prod_{m = 1}^k (A_m - 1) = p_s^{k}\cdot k!\,.\tag{1}$$

On the other hand, we have $A_k = p_s(p_s - 1) + 1 = p_s^2 - p_s + 1 < p_s^2$ and thus by the above

$$v_p(P_k) \leqslant \sum_{\ell = 1}^{\bigl\lfloor 2 \frac{\log p_s}{\log p}\bigr\rfloor}\biggl\lceil \frac{k}{p^{\ell}}\biggr\rfloor \leqslant \biggl\lfloor 2\frac{\log p_s}{\log p}\biggr\rfloor + \sum_{\ell = 1}^{\infty} \biggl\lfloor \frac{k}{p^{\ell}}\biggr\rfloor = \biggl\lfloor 2\frac{\log p_s}{\log p}\biggr\rfloor + v_p(k!)$$

for all primes $p \neq p_s$, hence

$$\prod_{p < p_s} p^{v_p(P_k)} \leqslant \prod_{p < p_s} \Bigl( p_s^2\cdot p^{v_p(k!)}\Bigr) = p_s^{2(s-1)}\cdot k!\,.\tag{2}$$

Also, none of the $A_m$ is divisible by $p_s$, whence $v_{p_s}(P_k) = 0$. Therefore it follows from $(1)$ and $(2)$ that

$$\prod_{p \leqslant n} p^{v_p(P_k)} < P_k$$

and consequently $P_k$ has a prime factor larger than $n$ as soon as $2(s-1) \leqslant k = p_s-1$, or equivalently $p_s \geqslant 2s - 1$. Which in fact holds for all $s$. And since a prime factor of $P_k$ divides at least one $A_m, \, 1 \leqslant m \leqslant k$ it follows that all prime factors of $P_k$ are $\leqslant A_k < p_s^2 \leqslant n^2$. So for $n \geqslant 2$ there always is at least one prime $q$ satisfying $n < q < n^2$ (or, slightly more tightly, $n < q \leqslant n^2 - n + 1$).