# Proofs from the BOOK: Bertrand's postulate: proof $\lfloor \frac{2n}{p^k} \rfloor - 2 \lfloor \frac{n}{p^k} \rfloor= 2$

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.

• Another way to see that the summands can be only 0 or 1 is using the lemma I wrote in my answer to your preceding question. Just use this lemma for $x=n/p^k$. – Martin Sleziak Nov 9 '11 at 17:11
• Thanks for refering to the other post, I will have a look at your Lemma :) – ulead86 Nov 9 '11 at 18:14

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.

• Ah thanks, but this is not the explanation for the addend being 1, isn't it? – ulead86 Nov 9 '11 at 9:06
• Well, if the inequality holds you see that the addend is < 2. It is either 0 or 1 then since the floors give you an integer. Therefore it is at most 1 – Alexander Vlasev Nov 9 '11 at 9:16
• Ah, right. Now I understood it. Thanks a lot. – ulead86 Nov 9 '11 at 9:27
• That is correct in idea but you have to be careful with the floors. If $p^k$ does not divide $n$ then you have two options. If $n < p^k$, then the floor will be $0$ and we are good. If $n > p^k$ we get $n = q\cdot p^k + r$ for some $0\leq r < p^k$ (by Euclidean division) and thus $-2\lfloor n/p^k\rfloor = -2\lfloor q + r/ p^k\rfloor = -2q$ since $r/p^k < 1$. The right-hand side is $-2(n/p^k-1) = -2(q+1/p^k-1)$. Since $1/p^k < 1$ we have $q+1/p^k-1 > q$ so multiplying by $-2$ we get $-2q < -2(q+1/p^k-1)$ and again, the strict inequality hold. Sorry if this is convoluted. – Alexander Vlasev Nov 9 '11 at 10:51
• Oh I'm sorry, it should read as "Since $1/p^k < 1$, that is $1/p^k - 1 < 0$ we have $q+1/pk−1 < q$ so multiplying by $−2$ we get $−2(q+1/pk−1) > −2q$ (because we are multiplying by a negative number)" – Alexander Vlasev Nov 10 '11 at 15:55