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