# Bertrand-Chebyshev Theorem/Lemma 2

## 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}$
$\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$