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.