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$

  • 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

1

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?