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.

  • 1
    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](http://math.stackexchange.com/questions/80175/proofs-from-the-book-bertrands-postulate-part-3-frac23np-leq-n-right/80176#80176). Just use this lemma for $x=n/p^k$.2011-11-09
  • 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
    Ah thanks, but this is not the explanation for the addend being 1, isn't it?2011-11-09
  • 2
    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 12011-11-09
  • 0
    Ah, right. Now I understood it. Thanks a lot.2011-11-09
  • 0
    Just to get it right: If we say, $p^k$ doesn't divide n, we get $-2 \lfloor \frac{p^k+l}{p^k} \rfloor = -2 \lfloor 1+\frac{l}{p^k} \rfloor = -2 -\frac{2l}{p^k}$ on the left side of the inequality. And on the right side we have $-(\frac{2l}{p^k})$. Then we see, that the left side is alway < then the right side.2011-11-09
  • 1
    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.2011-11-09
  • 0
    No, it'S very fine. Thanks for the long explanation and correcting my idea :)2011-11-09
  • 0
    Arg, one more question (sorry): How can you say that $q+\frac{1}{p^k}-1>q$, for me it's $q+\frac{1}{p^k}-12011-11-10
  • 1
    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)"2011-11-10
  • 0
    Thought something like that, just wanted to be sure :)2011-11-10