Bertrand-Chebyshev Theorem/Lemma 3
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$