Proof that it always exists a prime between $\sqrt n$ and $n$ I'm looking for a proof that ensures that for every natural number $n &gt; 1$ there is always a prime $p$ such that $\sqrt{n} \leq p \leq n$ holds.

I know you can deduce my previous claim as a corollary of some famous results like "Bertrand's postulate", but I was wondering if it does exist any easy self-contained proof.
This doesn't prove the claim for all $n&gt;2$, but it does show that there are at most finitely many counterexamples. I assume the Prime Number Theorem is allowed here (I know you want a self-contained proof, but this is the best I could do), I'm not sure how we could really do much without it.

Assume there are infinitely many $n \in \mathbb{N}$ such that $\pi(n)= \pi(\sqrt{n})$ and let $(n_i)_{i \in \mathbb{N}}$ be the ordered sequence of these natural numbers together with their square roots, so that $\pi(n_i)=\pi(\sqrt{n_i})$ for each $i$. We have, from the prime number theorem: $\displaystyle \lim_{x \to \infty} \frac{\pi(x) \log(x)}{x}=1$

In particular, this implies the following sequence converges: $( \frac{\pi(n_i) \log(n_i)}{n_i})_{i \in \mathbb{N}}$ and thus it must be Cauchy. So for every $\epsilon&gt;0$ there is an $N \in \mathbb{N}$ such that $\sqrt{n_i}=n_{k(i)}&gt;N$ implies:

$| \frac{\pi(n_i) \log(n_i)}{n_i}- \frac{\pi(\sqrt{n_i}) \log(\sqrt{n_i})}{\sqrt{n_i}}|&lt; \frac{\epsilon}{4}$

But $\pi(n_i)= \pi(\sqrt{n_i})$ for each $i$, so we can simplify this to:

$\pi(n_i)| \frac{(\sqrt{n_i}/\log(\sqrt{n_i}))-1}{n_i^{3/2}/ \frac{1}{2} \log(n_i)^2}|&lt; \frac{\epsilon}{4}$

Further simplification yields the following:

$\frac{1}{2}(\frac{\log(n_i)}{\sqrt{n_i}})(\frac{\log(n_i) \pi(n_i)}{n_i}) |\frac{\sqrt{n_i}}{\log(\sqrt{n_i})}-1|&lt; \frac{\epsilon}{4}$

Now, $\lim \frac{\log(n_i) \pi(n_i)}{n_i}=1$ again by the prime number theorem, so we can choose $N' \geq N$ sufficiently large such that $\frac{\log(n_i) \pi(n_i)}{n_i} \geq \frac{1}{2}$ for $n_i &gt;N'$. This gives us, for $n_i&gt; N'$:

$\frac{1}{4}(\frac{\log(n_i)}{\sqrt{n_i}})|\frac{\sqrt{n_i}}{\log(\sqrt{n_i})}-1|&lt; \frac{\epsilon}{4}$

So there is an $N' \in \mathbb{N}$ such that $n_i&gt;N'$ implies:

$|2-\frac{\log(n_i)}{\sqrt{n_i}}|&lt; \epsilon$

Since $\epsilon&gt;0$ was arbitrary, this by definition implies:

$\lim \frac{\log(n_i)}{\sqrt{n_i}}=2$

But in general: $\displaystyle \lim_{x \to \infty} \frac{\log(x)}{\sqrt{x}}=0$, so every sequence with $x_n \rightarrow \infty$ will satsify: $(\frac{\log(x_n)}{\sqrt{x_n}}) \rightarrow 0$, so our contradiction is obvious. 

So then by contradiction, there are at most finitely many $n \in \mathbb{N}$ such that $\pi(n)= \pi(\sqrt{n})$. $\Box$
No, there is no such a proof. Some years ago, I thought that there "must" be a proof of this fact, or to restate your proposition,
"There is always a prime between $n$ and $n^2$, when $n\geq 2$ "
should be proved using only combinatoric arguments and basic number theory. But I couldn't find such a proof and by the way, if you ever find such a proof, let me know, I will be very pleased too see it.