Bertrand-Chebyshev Theorem/Lemma 2

This article needs to be linked to other articles. You can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by adding these links. To discuss this page in more detail, feel free to use the talk page. When this work has been completed, you may remove this instance of {{MissingLinks}} from the code.

Lemma for Bertrand-Chebyshev Theorem

For all $m \in \N$:

$\ds \prod_{p \mathop \le m} p \le 2^{2 m}$

where the product is taken over all prime numbers $p \le m$.

Proof

It is plainly true for $m \le 2$; we will proceed by strong induction.

If $m > 2$ is even then:

\(\ds \prod_{p \mathop \le m} p\)

\(=\)

\(\ds \prod_{p \mathop \le m - 1} p\)

\(\ds \)

\(\le\)

\(\ds 2^{2 \paren {m - 1} }\)

by the induction hypothesis

\(\ds \)

\(<\)

\(\ds 2^{2 m}\)

By Sum of Binomial Coefficients over Lower Index:

$\ds \sum_{r \mathop = 0}^{2 k + 1} \binom {2 k + 1} r = 2^{2 k + 1}$

Therefore:

\(\ds \binom {2 k + 1} k + \binom {2 k + 1} {k + 1}\)

\(\le\)

\(\ds 2^{2 k + 1}\)

\(\text {(1)}: \quad\)

\(\ds \leadsto \ \ \)

\(\ds \binom {2 k + 1} k\)

\(\le\)

\(\ds 2^{2 k}\)

since $\ds \binom {2 k + 1} k = \binom {2 k + 1} {k + 1}$

If $m = 2 k + 1$ is odd, then all the prime numbers $k + 2 \le p \le 2 k + 1$ divide:

$\dbinom {2 k + 1} k = \dfrac {\paren {2 k + 1}!} {k! \paren {k + 1}!}$

Thus:

\(\ds \prod_{p \mathop \le m} p\)

\(=\)

\(\ds \prod_{p \mathop \le k + 1} p \prod_{k + 2 \mathop \le p \mathop \le 2 k + 1} p\)

\(\ds \)

\(\le\)

\(\ds \binom {2 k + 1} k \prod_{p \mathop \le k + 1} p\)

\(\ds \)

\(\le\)

\(\ds 2^{2 k} \prod_{p \mathop \le k + 1} p\)

by $(1)$

\(\ds \)

\(\le\)

\(\ds 2^{2 k} 2^{2 \paren {k + 1} }\)

by the induction hypothesis

\(\ds \)

\(=\)

\(\ds 2^{2 m}\)

$\blacksquare$