# How to show $\sum\limits_{i=1}^n\log\left(\frac{n}i\right)= \Theta(n)$?

Is the sum from i=1 to n for log(n/i) = Θ(n)?

Im studying for a test and appreciate your help. This is what I did: and got something else

$$\sum_{i=1}^n \log(n/i)=\sum_{i=1}^n[\log n-\log i]=\left(\sum_{i=1}^n\log n\right)-\left(\sum_{i=1}^n \log i\right)=n\log n-\log n!=\log\left(\frac{n^n}{n!}\right)$$

-

You did it all by yourself, really:
Stirling's formula shows that $n^n/n!\sim(2\pi n)^{-1/2}\mathrm e^{n}$, hence $\sum\limits_{i=1}^n\log(n/i)=\log(n^n/n!)$ (your post) and $$\log\left(n^n/n!\right)=n-\frac12\log(2\pi n)+o(1)=n+o(n)=\Theta(n).$$

Edit (without Stirling's formula)
Call $x_n=\sum\limits_{i=1}^n\log(n/i)=n\log(n)-\sum\limits_{i=1}^n\log(i)$, hence $$x_{n+1}-x_n=(n+1)\log(n+1)-n\log(n)-\log(n+1)=n\log(1+1/n).$$ Since $\log(1+u)=u+o(u)$ when $u\to0$, $x_{n+1}-x_n=1+o(1)$ when $n\to\infty$. This implies that $x_n=n+o(n)=\Theta(n)$.

-
Thank you!! but what is Stirling's formula?? is there another way?? – Mary Oct 20 '11 at 22:15
Did you check the link? – Did Oct 20 '11 at 22:17
@Didier: I think you will find $n^n \ge n!$ and $\log\left(n^n/n!\right) \approx +n$ – Henry Oct 20 '11 at 22:18
Checked the link. We didn't learn this formula so i guess there should be easier way to solve it. – Mary Oct 20 '11 at 22:21
Nusha, see edit. – Did Oct 20 '11 at 22:22

Hint: Use that

$$\sum_{i=1}^n \log i = \int_1^n \log x ~dx + O(1).$$

Since $\int_1^n \log x~dx = n \log n - n + o(1)$, this shows that

$$\sum_{i=1}^n \log (n/i) = n + O(1) = \Theta(n).$$

-
Thank you for your answer. I still don't understand..do i get here 1/n?anyway what is wrong with my way? why i dont get the right result? – Mary Oct 20 '11 at 21:57
@Nusha: Why do you want to get a $1/n$ factor? Do you know what $\Theta(n)$ means? Finally, your way doesn't get a wrong result, you just haven't got a result with your way. – anon Oct 20 '11 at 22:00
@Nusha: To find $\int_1^n \log x \;dx$, integrate by parts. If $u = \log x$ then you have $\int u\;dx = ux - \int x\;du$ etc. – Michael Hardy Oct 20 '11 at 22:00
right so i get ( correct me if im wrong) n(logn-1) and thats still give me Θ(nlogn). So is that false? – Mary Oct 20 '11 at 22:06
@Nusha: I have edited my post, and this should answer your questions. – JavaMan Oct 20 '11 at 22:16

What's your $Θ(n)$ function?

$\sum _{i=1}^n Log\left(\frac{n}{i}\right)=\log \left(\frac{n^n}{n!}\right)$

-
from that i gets Θ(nlogn) – Mary Oct 20 '11 at 22:02
@Nusha: That's incorrect. How did you get that? – anon Oct 20 '11 at 22:06