Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
1  
Take a look at this MSE page: math.stackexchange.com/questions/38917/… –  Eric Naslund Nov 8 '11 at 13:14
1  
Or better yet, take a look at this link on Robin Chapman's page: empslocal.ex.ac.uk/people/staff/rjchapma/etc/bertrand.pdf –  Eric Naslund Nov 8 '11 at 13:15
    
Thanks for the links, but I have to stick to the proof in the book... –  ulead86 Nov 8 '11 at 13:16

2 Answers 2

up vote 3 down vote accepted

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

share|improve this answer
    
Different formulation (and proof) of the above lemma can be found in this question: math.stackexchange.com/questions/84121/problem-about-x –  Martin Sleziak Nov 21 '11 at 18:24

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

share|improve this answer
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.) –  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
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. –  Martin Sleziak Nov 8 '11 at 14:29
    
Ah, thank you for the explanation :) –  ulead86 Nov 8 '11 at 14:33

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.