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.

A series of questions. Explanations would be useful. I have done the first four parts. I am confused on how to go about the last two.

  1. Show that for any prime $p$ the largest power of $p$ that divides $n!$ is $$ \left\lfloor \frac{n}{p}\right\rfloor +\left\lfloor \frac{n}{p^2} \right\rfloor +\cdots +\left\lfloor\frac{n}{p^r}\right\rfloor$$ where $p^r\le n < p^{r+1}$

  2. Use the basic definition (no induction) to show that for any $m \ge 1$, $\lfloor \frac{2n}{m}\rfloor \le 2\lfloor\frac{n}{m}\rfloor+1$

  3. Use the formula for $\binom{2n}{n}$ and the results of parts (1) and (2) to show that for any prime p, the largest power $p^r$ of $p$ that divides $\binom{2n}{n}$ satisfies $p^r\le 2n$

  4. Prove that for any integer $n\ge 1$, $\binom{2n}{n}\ge 2^n$

  5. Use the lower bound on the size of $\binom{2n}{n}$from part (4) and upper bound on each of its prime power factors from part (3) to prove that the number of distinct primes dividing $\binom{2n}{n}$ is at least $n/\log_2(2n)$

  6. Conclude that there are at least $n/\log_2(2n)$ primes less than $2n$

share|improve this question
2  
What have you tried? If you're stuck on #1, try investigating what happens for small values of $p$ and $n$. If you're completely stuck, you could still try #2, as it doesn't depend on #1. In fact the other questions don't depend on the proof of #1, just the formula presented. –  Shaun Ault Jan 25 '12 at 13:09
    
I'm sort of trying them all at once. I've got stuff written down that makes sense for 1 and 3 so far. –  020202002 Jan 25 '12 at 13:44
    
Do you think people here at MSE have no homeworks, and that every human being is supposed to do some home work and therefore you can assign us so many problems. Let me politely tell you that, the forum is to seek help in case you're stuck! Do not order us to "prove that..." and "Show that...". Further, we can help you in doing your homework if only you show us what you have done. Six problems are going to take us like an hour to TeX them up here! I hope that the community will share my feelings in this regards! –  user21436 Jan 25 '12 at 13:59
    
It was not so much intended as "do my homework" as much as it was "direct me to a proof of what looks like it could be a common result" –  020202002 Jan 25 '12 at 14:04
    
specifically though, i could use help with 5 and 6 –  020202002 Jan 25 '12 at 14:10
show 1 more comment

1 Answer

For part (5), suppose that $p_1^{r_1}\cdots p_k^{r_k}$ is the prime factorization of $\binom{2n}n$. From (3) you know that $p_i^{r_i}\le 2n$ for $i=1,\dots,k$, so

$$\binom{2n}n=\prod_{i=1}^kp_i^{r_i}\le(2n)^k\;.\tag{1}$$

Now combine $(1)$ with the inequality from part (4) and manipulate to see that $k\ge\dots$?

For part (6), if $p_i^{r_i}\le 2n$, how big can $p_i$ be?

share|improve this answer
add comment

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.