It's interesting to note that Chebyshev was the first to show Bertrand in 1850, and Erdos stated it elementarily in 1932 although it wasn't until 2006 when Bachraoui showed [itex][2n, 3n][/itex].

Another interesting thing is that Erdos checked the values for [itex]n = 1, 2, ..., 96[/itex], and Bachraoui had to check from 2 until 945. It is believed that in order to show each case you need to check exponentially many beginning cases.

You can find Bachraoui's proof via this URL:

http://www.m-hikari.com/ijcms-passwo...13-16-2006.pdf
The worst thing is, both Erdos and Bachraoui's proofs are simplistic by most proof techniques, yet Legendre's conjecture has been around for over 150 years.

Another interesting conjecture is by Dorin Andrica, who stated the following: For all [itex]n>0[/itex], let [itex]p_{n}[/itex] denote the n-th prime number, then [itex]\sqrt{p_{n+1}} - \sqrt{p_{n}} < 1[/itex]. In fact, if Andrica's Conjecture is proven, then Legendre is a direct corollary. I believe the converse is true as well, though I have been unable to find a proof on the internet.