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.

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

share|improve this question

3 Answers 3

up vote 8 down vote accepted

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)$.

share|improve this answer
    
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). $$

share|improve this answer
    
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)$

share|improve this answer
    
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

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.