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

Question

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

Did · Accepted Answer · 2011-10-20T22:21:31.667

9

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

edited Oct 20 '11 at 22:21

answered Oct 20 '11 at 22:14

Did

279,727

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
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
Why do we consider $x_{n+1} - x_{n}$ is that similar to the ratio test? – bigfocalchord Mar 10 '18 at 23:32
@bigfocalchord "Why do we consider" Because it works. "is that similar to the ratio test?" Not sure what you mean, please be more precise. – Did Mar 11 '18 at 07:05
@Did As in, what is the motivation of considering $x_{n+1}-x_{n}$ and I am wondering if it is similar to the ratio test (for series) where we consider $\frac{a_{n+1}}{a_n}$ where we consider the behaviour when $n \to \infty$ – bigfocalchord Mar 11 '18 at 08:39

JavaMan · Answer 2 · 2011-10-20T22:33:52.913

1

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

edited Oct 20 '11 at 22:33

answered Oct 20 '11 at 21:55

JavaMan

13,153

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

score 0 · Answer 3 · answered Oct 20 '11 at 22:00

0

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

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

answered Oct 20 '11 at 22:00

GarouDan

3,418

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

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

3 Answers3