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 > 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.
 A: This doesn't prove the claim for all $n>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>0$ there is an $N \in \mathbb{N}$ such that $\sqrt{n_i}=n_{k(i)}>N$ implies:
$| \frac{\pi(n_i) \log(n_i)}{n_i}- \frac{\pi(\sqrt{n_i}) \log(\sqrt{n_i})}{\sqrt{n_i}}|< \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}|< \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|< \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 >N'$. This gives us, for $n_i> N'$:
$\frac{1}{4}(\frac{\log(n_i)}{\sqrt{n_i}})|\frac{\sqrt{n_i}}{\log(\sqrt{n_i})}-1|< \frac{\epsilon}{4}$
So there is an $N' \in \mathbb{N}$ such that $n_i>N'$ implies:
$|2-\frac{\log(n_i)}{\sqrt{n_i}}|< \epsilon$
Since $\epsilon>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$
A: 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.
