3
$\begingroup$

Using the fact that $\log(n!) = n \log(n) - n + \mathcal{O}(\log(n))$ I am asked to show that:

$$ n \sum_{p \leq n} \frac{\log(p)}{p} = n \log(n) + \mathcal{O}(n) $$

Prior to this result it was shown that:

$$ \log(n!) = \sum_{p \leq n} \left( [n/p] + [n/p^2] + [n/p^3] + \dots \right) \cdot \log(p)$$

It is immediate that:

$$ n \log(n) - n + \mathcal{O}(\log(n)) = \sum_{p \leq n} \left( [n/p] + [n/p^2] + [n/p^3] + \dots \right) \cdot \log(p) $$

The quantity $\left( [n/p] + [n/p^2] + [n/p^3] + \dots \right)$ is the highest power of $p$ dividing $n!$. Obviously I have to get a $1/p$ into the sum somehow but it isn't clear to me what should replace the expression inside the sum. Any help would be appreciated.

  • 0
    Please avoid using `\displaystyle` in titles.2012-09-02
  • 3
    Does $[n/p]+[n/p^2]+\ldots \le \frac n{p-1}=\frac np+\frac n{p^2-p}$ help?2012-09-02
  • 0
    @ Hagen. That inequality seems very helpful. But I am being slow, why is $[n/p] + [n/p^2] + \dots \leq \frac{n}{p-1}$?. Also, my apologies @Asaf - why should \displaystyle not be used in titles?2012-09-02
  • 0
    It breaks the main page's structure, and it looks bad. Remember that the title is not only for this page, it appears in the list of active questions of the main page too.2012-09-02
  • 0
    Ah, I was not aware. Fair enough.2012-09-02
  • 0
    $[x]\le x$, then sum of a geometric series.2012-09-02
  • 0
    Of course! *facepalm* Thanks for the help Hagen and Gerry. I think I can go to sleep now. :D2012-09-02
  • 0
    Would you mind posting an answer?2013-05-21

0 Answers 0