Prove that there exists an $m$ such that for any $n>m$ there exists at least one prime between $c_n$ and $n$ Let $c_n$ be the $n$-th composite. Then the problem is to prove that-

$\pi(c_n)-\pi(n)>0$ $\forall n>m$

I have tried to progress in the problem using an elementary approach. So far I have been able to prove the following trivial results-


*

*For any $n>7$ the composite $c_n$ satisfies the inequality $2n>c_n>n$.

*$\pi(c_n)=c_n-n-1$

*$\pi(x)\geq \pi(p)$ $\iff$ $x \geq p$. Where $p$ is a prime. Notice that when the R.H.S always implies L.H.S. To prove the converse we note that $\pi(x) > \pi(p)$ $\implies$ $x>p$. The problem occurs when $\pi(x) = \pi(p)$. In that case if $x<p$ then it would imply that $\pi(x) < \pi(p)$, contradicting our hypothesis. Hence proved.

*The $\pi(c_n)$-th prime is strictly less then $c_n$ for any $n>7$.

*$c_n$$_-$$_\pi$$_($$_n$$_)$$_-$$_1$ $=$ $n-1$ $\iff$ $n$ is a prime and $c_n$$_-$$_\pi$$_($$_n$$_)$$_-$$_1$ $=$ $n$ $\iff$ $n$ is a composite.

*Using 5 it can be proved that $c_n$ $\geq$ $n+\pi(n)+1$.
But what I want is strict inequality. I have proved that the function $\Psi(n)=c_n-n-\pi(n)-1$ is increasing between two consecutive primes.  
Notice that the statement of the problem is equivalent to the following statement-

Prove that the $\pi(c_n)$-th prime is strictly greater then $n$ for any $n > m$.

Actually I have borrowed the problem from the AoPS site. For the actual post see http://www.artofproblemsolving.com/Forum/viewtopic.php?f=52&t=588724. 
 A: Currently, I do not have elementary solution, but I use Prime Number Theorem.
The version I use is:
$$
\pi(x)= \textrm{Li}(x) + O(x\exp(-c\sqrt{\log x}))$$
$$
=\frac{x}{\log x} + \frac{x}{\log^2 x} + O(\frac{x}{\log^3 x}).
$$
I tried using 2. of your observation. 
$$
\pi(c_n)=c_n-n-1.
$$
Thus, 
$$
c_n-n-1 = \frac{c_n}{\log c_n} + \frac{c_n}{\log^2 c_n} + O(\frac{c_n}{\log^3 c_n}).
$$
Then we have
$$
n=c_n-\frac{c_n}{\log c_n}-\frac{c_n}{\log^2 c_n} +O(\frac{c_n}{\log^3 c_n}).
$$
Now, we estimate $\pi(n)$ by the above formula:
$$
\pi(n)=\frac{ c_n-\frac{c_n}{\log c_n}-\frac{c_n}{\log^2 c_n} +O(\frac{c_n}{\log^3 c_n})}{\log( c_n-\frac{c_n}{\log c_n}-\frac{c_n}{\log^2 c_n} +O(\frac{c_n}{\log^3 c_n}))}+\frac{ c_n-\frac{c_n}{\log c_n}-\frac{c_n}{\log^2 c_n} +O(\frac{c_n}{\log^3 c_n})}{\log^2(c_n-\frac{c_n}{\log c_n}-\frac{c_n}{\log^2 c_n} +O(\frac{c_n}{\log^3 c_n}))}+O(\frac{ c_n-\frac{c_n}{\log c_n}-\frac{c_n}{\log^2 c_n} +O(\frac{c_n}{\log^3 c_n})}{\log^3(c_n-\frac{c_n}{\log c_n}-\frac{c_n}{\log^2 c_n} +O(\frac{c_n}{\log^3 c_n}))})
$$
$$
=\frac{c_n}{\log(c_n-\frac{c_n}{\log c_n}-\frac{c_n}{\log^2 c_n} +O(\frac{c_n}{\log^3 c_n}))}-\frac{c_n}{\log^2 c_n} + \frac{c_n}{\log^2 c_n} + O(\frac{c_n}{\log^3 c_n})
$$
$$
=\frac{c_n}{\log c_n} +O(\frac{c_n}{\log^3 c_n}).
$$
Therefore, 
$$
\pi(c_n)-\pi(n) = \frac{c_n}{\log^2 c_n}+O(\frac{c_n}{\log^3 c_n}).
$$
Since $c_n\rightarrow \infty$ as $n\rightarrow\infty$, we have the result. 
