It is known that the number $n!$ contains the prime factor $p$ exactly $$ \displaystyle\sum_{k\geq1}\left\lfloor\dfrac{n}{p^k}\right\rfloor $$

Then, if for a fixed prime $p$, define $R(p,n)$ to be the largest natural number $r$ such that $p^r$ divides ${2n \choose n}$, then: $$ R(p,n)=\displaystyle\sum_{j\geq1} \left \lfloor \dfrac{2n}{p^j} \right \rfloor -\color{blue}{2\displaystyle\sum_{j\geq1} \left \lfloor \dfrac{n}{p^j} \right \rfloor} $$ But each term of the last summation can either be zero or 1, (if $n/p^j \bmod 1< 1/2$) or $1$ (if $n/p^j \bmod 1\ge 1/2$) and all terms with $j>\log_p(2n)$ are zero. Therefore $$R(p,n)\leq \log_{p}(2n)$$

I don't understand the $\color{blue}{\mbox{blue}}$ lines, how can I get it?

  • $\begingroup$ If I want $\max r$, why I rest the blue summation? the blue sumation is the max power which divides $n!\times n!$, if I want the maximum would be better not to take the minimum exponent wich divides $n!\times n!$ to maximize the sum? $\endgroup$ – Luis Felipe May 18 '15 at 1:18
  • 1
    $\begingroup$ $x\bmod 1\ge 1/2$ is an excessively fancy way of saying that the fractional part of $x$ (the part after the decimal point) is $\ge 1/2$. $\endgroup$ – André Nicolas May 18 '15 at 1:22
  • $\begingroup$ Thank you, now it has color black. $\endgroup$ – Luis Felipe May 18 '15 at 1:24
  • $\begingroup$ You are welcome. The $x\bmod r$ notation sort of makes sense. For $x=(q)(1)+r$, for some integer $q$, and some $r$ with $0\le r\lt 1$. So the fractional part is (sort of) the "remainder" on division by $1$. $\endgroup$ – André Nicolas May 18 '15 at 1:32
  • $\begingroup$ sure, I read the $mod$ notation only with an integer modulus. I'm reading about Bertrand postulate proof from Erdös. $\endgroup$ – Luis Felipe May 18 '15 at 1:34

If $j \gt \log_p(2n)$, then $p^j \gt 2n$. It follows that $\frac{2n}{p^j}\lt 1$, and therefore $\left\lfloor \frac{2n}{p^j}\right\rfloor=0$. For $j \gt \log_p(2n)$, all the terms in the "infinite" sums of your second displayed formula are $0$.

  • $\begingroup$ Thank you, I've realised why holds the first summation $\endgroup$ – Luis Felipe May 18 '15 at 1:55

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.