2
$\begingroup$

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$

  • 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.2012-01-25
  • 0
    I'm sort of trying them all at once. I've got stuff written down that makes sense for 1 and 3 so far.2012-01-25
  • 0
    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!2012-01-25
  • 0
    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"2012-01-25
  • 0
    specifically though, i could use help with 5 and 62012-01-25
  • 1
    @020202002, if that is the case, **please** make it explicit in the question. Explain what you have tried, how you have handled the previous parts, &c: show that you have actually done your homework.2012-01-25

1 Answers 1