I was checking out the Wikipedia article on the proof of Bertrand's Postulate.

For Lemma 4, the argument is made for $x\ge 3, x\#<2^{2x-3}$

Here's the proof by induction:

  • $n = 3$: $n\# = 6 < 8$
  • $n = 4$: $n\# =6 < 32$
  • If $n$ odd, $n = (2m-1)\# < 2^{2(2m-1)-3}$
  • If $n$ even, $n = (2m)\# < 2^{2(2m)-3}$
  • $n\# < 2^{2n-3}$

Thus the lemma is proven.

I am assuming that there is a correct way to state this proof. Proof by induction would mean that we assume that the basis is true up to $n$ and then we show if it is true for $n$, it is true for $n+1$.

The basis is $n=3$ and $n=4$.

The inductive step is stated without proof. Am I correct? Or is this point referring to a well known result?

Edit: As I thought about it, it seems to me that the $2n-3$ part is arbitrary. For example, it is easy to make an argument for $2n-5$. I wanted to check if my reasoning is correct about this.

Here is the argument for $n \ge 4$:

(1) $2^{2(4)-5} = 2^{3} = 8 > 4\# = 6$

(2) Assume it is true up to $n-1$ where $(n-1) > 4$

(3) if $n$ is even, it is true since $n\# = (n-1)\#$ so we can assume $n$ is odd.

(4) There exists $m$ such that $n = 2m-1$

(5) $(1+1)^{2m-2} = \dfrac{1}{2}\sum\limits_{i=0}^{2m-1}{{2m-1}\choose{i}} = \sum\limits_{i=0}^{m-1}{{2m-1}\choose{i}} > \dfrac{(2m-1)!}{(m)!(m-1)!} > \dfrac{(2m-1)\#}{m\#}$

(6) $(m\#)(2)^{2m-2} > (2m-1)\#$

(7) Since by assumption, $m\# < 2^{2m-5}$, we have:

$$2^{2m-5}\cdot2^{2m-2} = 2^{4m-7} = 2^{2(2m-1)-5} > (2m-1)\# = n\#$$

Is something in my argument wrong? If not, I suspect that I can go lower than $5$ to any arbitrary number that I wish (so long as I keep increasing $n$. So, something is probably wrong. If you can let me know, I would appreciate it.

  • 1
    $\begingroup$ I agree. I'm hoping that it is correct. I'm working on the explanation. If I find a way to prove it, I'll edit my question and post the reasoning. $\endgroup$ – Larry Freeman Feb 1 '15 at 7:09
  • 1
    $\begingroup$ I think $2^{2(2m-3)}$ should be $2^{2(2m)-3}.$ Just a typo in the article. $\endgroup$ – daniel Feb 1 '15 at 8:52
  • 2
    $\begingroup$ Here is a link to Erdos' article. renyi.hu/~p_erdos/1989-29.pdf. The discussion is in the first couple of pages. His proof in form is pretty much that of the Wiki article. In Erdos' proof by assuming $p<n$ he shows $\geq n+1.$ That is the induction. $\endgroup$ – daniel Feb 1 '15 at 9:16
  • 3
    $\begingroup$ There are essentially two kinds of people who mess up Wikipedia articles: those who honestly think they're improving the article, and those who are deliberately trying to put mistakes into it. Changing $4^n$ to $2^{2m - 3}$ strikes me as coming from someone who honestly thought this was better but didn't think it through. $\endgroup$ – Robert Soupe Feb 1 '15 at 20:11
  • 1
    $\begingroup$ @RobertSoupe: I was thinking the same thing. It's nice to have a solid reference, which the $4^n$ version was. $\endgroup$ – daniel Feb 2 '15 at 3:44

Your Answer

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

Browse other questions tagged or ask your own question.