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

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

  • 1
    Take a look at this MSE page: http://math.stackexchange.com/questions/38917/are-there-any-combinatoric-proofs-of-weak-versions-of-bertrands-postulate2011-11-08
  • 1
    Or better yet, take a look at this link on Robin Chapman's page: http://empslocal.ex.ac.uk/people/staff/rjchapma/etc/bertrand.pdf2011-11-08
  • 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

  • 2
    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.)2011-11-08
  • 0
    Hi Martin, thanks for your time and effort. I thought the same, so next time, I open a new question. Sorry for that.2011-11-08
  • 0
    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$$?2011-11-08
  • 1
    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.2011-11-08
  • 0
    Ah, thank you for the explanation :)2011-11-08