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
    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. – Larry Freeman Feb 1 '15 at 7:09
  • 1
    I think $2^{2(2m-3)}$ should be $2^{2(2m)-3}.$ Just a typo in the article. – daniel Feb 1 '15 at 8:52
  • 2
    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. – daniel Feb 1 '15 at 9:16
  • 1
    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. – Robert Soupe Feb 1 '15 at 20:11
  • 1
    @RobertSoupe: I was thinking the same thing. It's nice to have a solid reference, which the $4^n$ version was. – daniel Feb 2 '15 at 3:44

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.