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.

| cite | improve this question | | | | |
$\endgroup$
  • 1
    $\begingroup$ 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$. $\endgroup$ – Martin Sleziak Nov 9 '11 at 17:11
  • $\begingroup$ Thanks for refering to the other post, I will have a look at your Lemma :) $\endgroup$ – ulead86 Nov 9 '11 at 18:14
4
$\begingroup$

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.

| cite | improve this answer | | | | |
$\endgroup$
  • $\begingroup$ Ah thanks, but this is not the explanation for the addend being 1, isn't it? $\endgroup$ – ulead86 Nov 9 '11 at 9:06
  • 2
    $\begingroup$ 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 $\endgroup$ – Alexander Vlasev Nov 9 '11 at 9:16
  • $\begingroup$ Ah, right. Now I understood it. Thanks a lot. $\endgroup$ – ulead86 Nov 9 '11 at 9:27
  • 1
    $\begingroup$ 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. $\endgroup$ – Alexander Vlasev Nov 9 '11 at 10:51
  • 1
    $\begingroup$ 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)" $\endgroup$ – Alexander Vlasev Nov 10 '11 at 15:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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