Proving $p_{n+1}How can we prove that 
$$p_{n+1}<p_n^2$$
Where $p_n$ is the nth prime number.
Using Bertrand's Postulate it becomes easy. But how can we prove it without using this deep result?
 A: Chebychev proved that
there are constants such that
$a < \dfrac{\pi(x)\ln(x)}{x} < b$.
https://www.encyclopediaofmath.org/index.php/Chebyshev_theorems_on_prime_numbers
From this,
your result follows
for large enough $n$.
A: By this answer I am trying to establish a start for more argument for evolution of proposed algorithm in this post.
One method to show $ p_{n+1} < p_n^2$ is to show that there is some primes between $p_{n+1}$ and $p_n^2$.Experimentally we can see that there are infinitely many primes like $p_n$ such that $p_n^2-2k$ is prime,for example:
$p_n = 5 ⇒ p=5^2-2=23 $
$p_n = 7 ⇒ p=7^2-2=47 $
$p_n = 11 ⇒ p=2^2-2\times 4=113 $
This fact shows that $p=p_n^2-2k ⇒ p_n  < p < p_n^2$
Now if there is a prime between $p_n$ and $p_n^2$  then we must have:
$p_n^2-2k=p_n +2 k_1$ ⇒ $p_n=\frac{1± \sqrt{1+8(k+k_1)}}{2}$
Bellow is a list for comparison:
$k+k_1 =1,...3,...6,...10,...15,.....21,....55,...78$
$\Delta=.....9,..25,....49,..81,..121,...169,...441....625$
$p_n=.... 2,...3,.........5,............7,.....11....13$
$p_n^2=....4,...9,.........25,..........49,....121,..169$
The equation $p_n^2-2k=p_n +2 k_1$ has integer solutions and is a prime generator which gives all primes for suitable values of $k$ and $k_1$. The table shows that the possibility of existence of primes between $p_n$ and$p_n^2$ is not zero, that is there is a prime subsequent to $p_n$ i.e. $p_{n+1}$ so that $p_n < p_{n+1} < p_n^2$
A: Using the fact that $\pi(x)>\sqrt{x}$ from some $x_0$ onwards (use this link asa a reference to references), where $\pi(x)$ is the prime counting function, we have 
$$n+1=\pi(p_{n+1})>\sqrt{p_{n+1}} \iff (n+1)^2 >p_{n+1}$$
From the other point of view $p_n\geq n+1$, this can be easily proved by induction:


*

*$p_1=2\geq 1+1$

*from $p_n\geq n+1 \Rightarrow p_n+1\geq n+2 \Rightarrow p_{n+1}>p_n+1\geq n+2$ (simply because $p_n+1$ can not be prime for $n>1$ since it's even).


Altogether
$$p_n^2 \geq (n+1)^2 > p_{n+1} \tag{1}$$
At this point, I should stress the fact that we started with $\pi(x)>\sqrt{x}$ being valid from some $x_0$ onwards. So, $(1)$ is valid from that $x_0$ onwards. But the values $n<x_0$ can be validated manually or with a computer program. Wikipedia, for example, suggests
$$\pi(x)>\frac{x}{\log{x}}\left(1+\frac{1}{\log{x}}\right)>\frac{x}{\log{x}}> \sqrt{x}, \forall x\geq599$$
