Bertrand-Chebyshev Theorem/Lemma 3

From ProofWiki
Jump to navigation Jump to search

Lemma

Let $p$ be a prime number.

Let $p^k \divides \dbinom {2 n} n$.

Then $p^k \le 2 n$.


Proof

Let $l$ be the largest power of $p$ with $p^l \le 2 n$.

By De Polignac's Formula, the largest power of $p$ dividing $n!$ is $\ds \sum_{i \mathop \ge 1} \floor {\frac n {p^i} }$.

So:

\(\ds k\) \(\le\) \(\ds \sum_{i \mathop \ge 1} \floor {\frac {2 n} {p^i} } - 2 \sum_{i \mathop \ge 1} \floor {\frac n {p^i} }\) Largest power of $p$ dividing $\dbinom {2 n} n$
\(\ds \) \(=\) \(\ds \sum_{i \mathop = 1}^l \paren {\floor {\frac {2 n} {p^i} } - 2 \floor {\frac n {p^i} } }\) as terms with $i > l$ are zero
\(\ds \) \(\le\) \(\ds \sum_{i \mathop = 1}^l 1\) because $\floor {2 x} - 2 \floor x \le 1$
\(\ds \) \(=\) \(\ds l\)

$\Box$