# Bertrand's postulate proof

I think the last inequality should be $4^{n/3}\le(2n+1)(2n)^{\sqrt{2n}}$. But even when the RHS is decreased from $(2n+1)(2n)^{\sqrt{2}n}$, the RHS still dominates the LHS for $n>>0$ (you can check with wolfram alpha: http://www.wolframalpha.com/input/?i=%282n%2B1%29%282n%29^{sqrt%282n%29}+-+4^{n%2F3} ).

Wolframalpha only shows values for small $n$, a smooth graph around $0$ doesn't necessarily predict what happens at $\infty$. Note that the standard plots in WA are for $-15 \leq n \leq 15$ which is very far from $n > > 0$.

$$4^{n/3}\le(2n+1)(2n)^{\sqrt{2n}} \Leftrightarrow n \frac{\ln(4)}{3} \leq \ln(2n+1)+\sqrt{2n} \left(\ln(2n)\right) (*)$$

Now use that $\ln(n) < < n^{\frac{1}{4}}$ for $n$ large enough to get a contradiction.

Added To clarify a little on the choice $n> 2048$ in the proof. Note that while WA shows that the graph seems to fail around $460$, a finite WA plot is NOT a proof, since the graph could also come back up. And WA was not available to Chebashev.

One needs to effectively prove that $(*)$ fails for $n > N$. Here is a proof for $N=2048$, the person which wrote the wiki article probably had something similar in mind.

I am going to switch from $\ln$ to $\log_2$.

Claim: For $n >2048$ we have

$$n \frac{\log_2(4)}{3} > \log_2(2n+1)+\sqrt{2n}\left(\log_2(2n)\right) (*)$$

Proof:

Let $k$ be the integer so that $k \leq \log_2(n) < k+1$.

Then

$$\frac{2}{3} n \geq \frac{2^{k+1}}{3}$$ $$\log_2(2n+1)+\sqrt{2n}\left(\log_2(2n)\right) < k+2 + 2^{\frac{k+2}{2}}\cdot (k+2)$$

let $m=k+2$. If we can show that for all $m \geq 11$ we have

$$\frac{2^m}{6} \geq m(2^{m/2}+1)$$

we are done.

This is equivalent to

$$2^m \geq 6m (2^{m/2}+1)$$

As $6m(2^{m/2}+1)< 6m( (2^{m/2}+2^{m/2})=12m2^{m/2}$$this follows immediately from$$2^{m/2} \geq 12 m$$which is an easy induction problem. • Here is a WolframAlpha plot of the difference of logarithms over a larger range. – Dan Brumleve Aug 10 '13 at 20:00 • So it seems the inequality fails for$n$around$460$. Then why did the original article say$2048$? – user70520 Aug 10 '13 at 21:56 • @user70520 The main idea of the proof works for$n > N$for some$N$. Up to$N$it needs to be checked by hand. Now, particular values of$N$vary from proof to proof, depending of the techniques and approximations used ( I saw a proof with better approximations which worked for$n \geq 128$). But the actual value of$N$is really irrelevant to the proof, it only matters for the step where you actually prove that the above inequality fails.... The larger$N\$ is the easier it is to prove it... – N. S. Aug 10 '13 at 22:11