2
$\begingroup$

I have a very hard proof from "Proofs from the BOOK". It's the section about Bertrand's postulate, page 9:

It's at the top of the page. We want to know, how often the prime factor p divides $\binom{2n}{n}$. Legendre gives us the solution $\sum_{k \geq 1} \lfloor\frac{2n}{p^k}\rfloor - 2 \lfloor \frac{n}{p^k} \rfloor$ Now the author says, that every addend is max. 1, because we have $\lfloor\frac{2n}{p^k}\rfloor - 2 \lfloor \frac{n}{p^k} \rfloor < \frac{2n}{p^k}-2 \left( \frac{n}{p^k} - 1 \right) = 2$ and the addend is a integral number.

I understood the proof including the sum, but why I leave out the floors in the inequality and why is every addend 1?

Any help is appreciated.

  • 0
    Thanks for refering to the other post, I will have a look at your Lemma :)2011-11-09

1 Answers 1

4

Leaving out the floors has to do with the facts that

$\lfloor x \rfloor \leq x \quad \text{and} \quad -\lfloor x \rfloor \leq -(x-1) $

for positive $x$. Now we need at least one of these to be a strict inequality to obtain the inequality in the problem. However this is not too bad because we have two easy cases. If $p^k$ evenly divides $n$ we can immediately remove the floors and the term is $0$. If $p^k$ does not divide $n$ evenly the term $n/p^k$ is not an integer and we have

$ -2\left\lfloor \frac{n}{p^k}\right\rfloor < -2\left(\frac{n}{p^k}-1\right),$

making the inequality strict.

  • 0
    Thought something like that, just wanted to be sure :)2011-11-10