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<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 :-)

$\endgroup$
3
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$
  • 2
    $\begingroup$ 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.) $\endgroup$ – Martin Sleziak Nov 8 '11 at 13:48
  • $\begingroup$ Hi Martin, thanks for your time and effort. I thought the same, so next time, I open a new question. Sorry for that. $\endgroup$ – ulead86 Nov 8 '11 at 13:56
  • $\begingroup$ 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$$? $\endgroup$ – ulead86 Nov 8 '11 at 14:16
  • 1
    $\begingroup$ 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. $\endgroup$ – Martin Sleziak Nov 8 '11 at 14:29
  • $\begingroup$ Ah, thank you for the explanation :) $\endgroup$ – ulead86 Nov 8 '11 at 14:33

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.