7
$\begingroup$

Prove that if $p^{a}$ is a factor of the canonical factorization of ${{2n}\choose{n}}$ then $p^{a} < 2n$?

My attempt:

$${{2n}\choose{n}} = \frac{(2n)!}{n!n!}$$

Let $a_1$ be the highest of power of $(2n)!$
Let $a_2$ be the highest of power of $n!$

So the highest power of $\frac{(2n)!}{n!n!}$ = $a_1 - 2a_2$

where $a_1 <= 2n - 1$ and $2a_2 <= 2n - 2$
Therefore the highest power of $p$ that divides $\frac{(2n)!}{n!n!}$ is $2n - 1 - 2n + 2 = 1$.

Since $a <= 1 \implies p^{a} < 2n$

Am I in the right track? Any idea?

Update

Following Ross Millikan's hint:

Let $a$ be the highest power of $p$ such that $p^{a}|n!$ Then, $a$ = $\lfloor \frac{n}{p} \rfloor + \lfloor \frac{n}{p^2} \rfloor +\lfloor \frac{n}{p^3} \rfloor + \ldots \lfloor \frac{n}{p^k} \rfloor$

Let $b$ be the highest power of $p$ such that $p^{b}|(2n)!$ Then, $b$ = $\lfloor \frac{2n}{p} \rfloor + \lfloor \frac{2n}{p^2} \rfloor +\lfloor \frac{2n}{p^3} \rfloor + \ldots \lfloor \frac{2n}{p^q} \rfloor$

$\Longrightarrow b - 2a$ is the highest power of $p$ such that $p|\frac{(2n)!}{n!n!}$

Where $a, b \in N \implies b - 2a < b$
Besides, $p^{b} < 2n$
$\therefore p^{b - 2a} < p^{b} < 2n$

Am I in the right track now?

Thanks,
Chan

  • 0
    You can't go from $a_1 \le 2n - 1$ and $2a_2 \le 2n - 2$ to $a_1-a_2\le (2n-1) - (2n-2)$. You can add two inequalities, but not subtract them. For example, 3<4 and 2<10, but (3-2) is not less than (4-10).2011-02-22
  • 3
    Giving a hint rather than a full solution: The number of times that p divides $\binom{2n}{n}$ is $\sum_{k\geq 1} \lfloor (2n)/p^k \rfloor - 2 \lfloor n/p^k \rfloor$ where $\lfloor x \rfloor$ is the "round down" function. Which of these terms can be nonzero? How do they cancel?2011-02-22
  • 0
    Also, it appears numerically that if $p^a$ is a factor of ${n \choose k}$, then $p^a \le n$; that is, this doesn't depend on the fact that ${2n \choose n}$ is a "central" binomial coefficient. So once you come up with a proof, see if it can work on general binomial coefficients as well.2011-02-22
  • 0
    @David Speyer: Thanks.2011-02-22
  • 0
    @Michael Lugo: Thanks.2011-02-22
  • 0
    @Chan: sounds like you didn't actually have to compute $a$ and $b$ to get to the conclusion.2011-02-23
  • 0
    @Weltschemerz: Thanks for the comment. Yes, I did not compute a and b. How does it look to you?2011-02-23

2 Answers 2

2

Hint: The highest power of a prime,$p$, that divides $n!$ is $\lfloor \frac{n}{p} \rfloor + \lfloor \frac{n}{p^2} \rfloor +\lfloor \frac{n}{p^3} \rfloor + \ldots \lfloor \frac{n}{p^k} \rfloor$. This is your $a_2$. Can you compare twice this with the expression for $2n$, your $a_1$?

  • 0
    Many thanks for such a great hint ;)2011-02-22
4

Here's a way I like a lot, I have outlined the steps: (Each step is a one line proof)

(i) There are $\lfloor N/q \rfloor$ integers less than or equal to $N$ that are divisible by $q$.

(ii) Deduce that the difference in the number of integers in the numerator and denominator of $\left({2N\atop N}\right)$ which are divisible by $q$ is $\lfloor 2N/q\rfloor -2\lfloor N/q\rfloor$.

(iii) Show that this quantity equals either 0 or 1.

(iv) Deduce that if $p^r$ divides $\left({2N\atop N}\right)$ then $p^r\leq 2N$.

Hope that helps,

Remark: This is an exercise I did a while ago from a book by Dr. Andrew Granville. It had similar outline, and was not my invention.

  • 0
    Thanks a lot for your great hint.2011-02-22