# Proofs from the BOOK: Bertrand's postulate Part 3: $\frac{2}{3}n<p \leq n \rightarrow$ no p divides $\binom{2n}{n}$

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<p \leq 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<p \leq 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 :-)

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<p\le n$.

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$$

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<p \leq 2n} p$$

The author leaves out $\frac{2}{3}n<p\leq 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

• I believe that it would be better to edit your original question and add this there than to post a complementary question as a new answer. (It does not matter so much, but making a habit of this would not be a good thing.) – Martin Sleziak Nov 8 '11 at 13:48
• Hi Martin, thanks for your time and effort. I thought the same, so next time, I open a new question. Sorry for that. – ulead86 Nov 8 '11 at 13:56
• Just to get it right: Because $a(p) \leq max\{r;p^r \leq 2n\}$ I can write $$\prod_{p \leq \sqrt{2n}} 2n$$ and not $$\prod_{p \leq \sqrt{2n}} p$$? – ulead86 Nov 8 '11 at 14:16
• I would say that $\prod_{p\le\sqrt{2n}} p^{a(p)}$ can be estimated by $\prod_{p\le\sqrt{2n}} 2n$ - see my last edit. With the exception of the missing exponent I agree with what you wrote. – Martin Sleziak Nov 8 '11 at 14:29
• Ah, thank you for the explanation :) – ulead86 Nov 8 '11 at 14:33