Bertrand-Chebyshev Theorem/Lemma 2

From ProofWiki
Jump to navigation Jump to search

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$