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

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

-
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). – Ross Millikan Feb 22 '11 at 1:50
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? – David Speyer Feb 22 '11 at 2:43
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. – Michael Lugo Feb 22 '11 at 3:38
@David Speyer: Thanks. – Chan Feb 22 '11 at 5:39
@Michael Lugo: Thanks. – Chan Feb 22 '11 at 5:40

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$?

-
Many thanks for such a great hint ;) – Chan Feb 22 '11 at 4:29

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.

-
Thanks a lot for your great hint. – Chan Feb 22 '11 at 4:30