6
$\begingroup$

I want to show that every prime power $p^k$ that divides $\binom{2m}{m}$ is smaller than or equal to $2m$.

As a first step, I looked at $$\binom{2m}{m} = \frac{(2m)!}{(m!)^2} = \frac{2m(2m-1) \ldots (m+2)(m+1)}{m!} \, .$$ Here I'm essentially stuck. I can apply the prime factorization to numerator and denominator, then I can cancel and I know that $p^k$ is left over in the numerator. But I cannot conclude $p^k \leq 2m$.

I feel that some vital ingredient is missing here, but I don't know what it is.

(Post edited with respect to the helpful comment.)

$\endgroup$
  • 1
    $\begingroup$ $\binom 21=2$ is an exception $\endgroup$ – Mark Bennet May 27 '14 at 17:41
  • $\begingroup$ Oh, you're right. It's supposed to be "smaller or equal" and $p^k \leq 2m$. I dropped that because I wasn't aware of the exception. Thanks. $\endgroup$ – Amarus May 27 '14 at 18:11
2
$\begingroup$

Hint: Let $\alpha_{n, p}$ be the largest natural number such that $p^{\alpha_{n, p}}\mid n!$ for $n\in\mathbb{N}$ and $p$ prime. Then $$\alpha_{n, p}=\sum_{k=1}^{\infty}{\left[\frac{n}{p^k}\right]},$$ where $[x]$ is the integer part of $x$.

$\endgroup$
  • $\begingroup$ Does that help, @Amarus? $\endgroup$ – Shaun May 27 '14 at 18:46
  • 1
    $\begingroup$ I'm still trying to figure it out. We want to count with what multiplicity $p$ occurs in the prime factorization of $n! \,$. $\left\lfloor \frac{n}{p} \right\rfloor$ is the number of elements in $\left\{1, \ldots, n\right\}$ that are divided by $p$ at least once, $\left\lfloor \frac{n}{p^2} \right\rfloor$ the number of such elements that are divided by $p$ at least two times and so on. So we can add those up until $\left\lfloor \frac{n}{p^k} \right\rfloor$ is less than $1$ to obtain the number of occurences of $p$ in the prime factorization of $n!\,$. Is that about right? $\endgroup$ – Amarus May 27 '14 at 20:47
  • $\begingroup$ Yeah, exactly :) $\endgroup$ – Shaun May 27 '14 at 20:50
  • $\begingroup$ (If this answers your question, please don't forget to accept it by clicking the tick $\ddot\smile$) $\endgroup$ – Shaun May 28 '14 at 13:36
  • 1
    $\begingroup$ Another hint: consider $$\alpha_{2n, p}.$$ $\endgroup$ – Shaun May 31 '14 at 10:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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