Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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
up vote 4 down vote accepted

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.

share|cite|improve this answer
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 – Aleks 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. – Aleks 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)" – Aleks Vlasev Nov 10 '11 at 15:55

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.