3
$\begingroup$

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

I have to show, that for $\frac{2}{3}n

there is no p which divides $\binom{2n}{n}$. I know $\binom{2n}{n}=\frac{(2n)!}{n!n!}$ and from $\frac{2}{3}n

I follow $3p>2n$. Then $(2n)!$ has only the prime factors $p$ and $2p$ (because 3p>2n) and $n!$ has only the prime factor $p$. At this point the author goes on to the next part of the proof.

Can someone explain to me, how the argument about the p's proofs the statement, that there is no $p$ which divides $\binom{2n}{n}$?

I hope my question is clear and sorry for my bad English. Thanks in advance :-)

  • 0
    Thanks for the links, but I have to stick to the proof in the book...2011-11-08

2 Answers 2

3

Lemma: $\lfloor 2x \rfloor - 2\lfloor x \rfloor = \begin{cases} 1 & \frac12<\{x\}, \\ 0 & 0\le \{x\} \le \frac12. \end{cases}$

Here $\{x\}$ denotes the fractional part of $x$.


Now if you already know (from the preceding part of the proof) that the exponent of $p$ is $\left\lfloor \frac{2n}p \right\rfloor - 2\left\lfloor \frac np \right\rfloor$ then you can use the above lema for $x=\frac np$.

Namely, it is zero whenever $1\le \frac np < \frac32$, which is equivalent to $\frac23n.


Note that in that part of the proof you already assume that $p>\sqrt{2n}$, so there is at most one non-zero summand in the sum $\sum_{k\ge 1}\left\lfloor \frac{2n}{p^k} \right\rfloor - 2\left\lfloor \frac n{p^k} \right\rfloor$

  • 0
    Different formulation (and proof) of the above lemma can be found in this question: http://math.stackexchange.com/questions/84121/problem-about-x2011-11-21
1

Ok, got it. One more question: Further down on the page we have

$\frac{4^n}{2n} \leq \binom{2n}{n} \leq \prod_{p \leq \sqrt{2n}} 2n * \prod_{\sqrt{2n} < p \leq \frac{2}{3}n} p * \prod_{n

The author leaves out $\frac{2}{3}n because there are no p's. But what is the reason he writes $\prod_{p \leq \sqrt{2n}} 2n$ All the other products are with $p$ which is understandable, so why not in the first one?

Greetings, Daniel


Let us denote $a(p)$ the exponent of $p$ in $\binom{2n}n$. The inequality $p^{a(p)} \le 2n$ follows from $a(p)\le \max \{r; p^r\le 2n\}$. (Note that this inequality is mentioned in the proof.)

The proof of the last inequality: We have $a(p)=\sum_{k\ge 1}\left\lfloor \frac{2n}{p^k} \right\rfloor - 2\left\lfloor \frac n{p^k} \right\rfloor$ and the summand is zero for $k> \max\{r; p^r\le 2n\}$ and all summands are at most one. So we have $a(p) \le \sum_{k; p^k\le 2n} 1 = \max \{r; p^r\le 2n\}.$

Therefore we have $\prod_{p\le\sqrt{2n}} p^{a(p)} \le \prod_{p\le\sqrt{2n}} 2n.$

Greetings,
Martin

  • 0
    Ah, thank you for the explanation :)2011-11-08