Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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
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? –  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
show 2 more comments

2 Answers

up vote 2 down vote accepted

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

share|improve this answer
    
Many thanks for such a great hint ;) –  Chan Feb 22 '11 at 4:29
add comment

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.

share|improve this answer
    
Thanks a lot for your great hint. –  Chan Feb 22 '11 at 4:30
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.