3
$\begingroup$

Regarding http://michaelnielsen.org/polymath1/index.php?title=Bertrand%27s_postulate

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} ).

This doesn't give any contradiction.

$\endgroup$
4
$\begingroup$

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$.

About that inequality:

$$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.

$\endgroup$
  • $\begingroup$ Here is a WolframAlpha plot of the difference of logarithms over a larger range. $\endgroup$ – Dan Brumleve Aug 10 '13 at 20:00
  • $\begingroup$ So it seems the inequality fails for $n$ around $460$. Then why did the original article say $2048$? $\endgroup$ – user70520 Aug 10 '13 at 21:56
  • $\begingroup$ @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... $\endgroup$ – N. S. Aug 10 '13 at 22:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.