5
$\begingroup$

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

3 Answers 3

8

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

  • 0
    Thank you!! but what is Stirling's formula?? is there another way??2011-10-20
  • 0
    Did you check the link?2011-10-20
  • 0
    Checked the link. We didn't learn this formula so i guess there should be easier way to solve it.2011-10-20
  • 0
    Nusha, see edit.2011-10-20
  • 0
    Why do we consider $x_{n+1} - x_{n}$ is that similar to the ratio test?2018-03-10
  • 0
    @bigfocalchord "Why do we consider" Because it works. "is that similar to the ratio test?" Not sure what you mean, please be more precise.2018-03-11
  • 0
    @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$2018-03-11
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). $$

  • 0
    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?2011-10-20
  • 0
    @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.2011-10-20
  • 0
    @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.2011-10-20
  • 0
    right so i get ( correct me if im wrong) n(logn-1) and thats still give me Θ(nlogn). So is that false?2011-10-20
  • 0
    @Nusha: I have edited my post, and this should answer your questions.2011-10-20
0

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

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

  • 0
    from that i gets Θ(nlogn)2011-10-20
  • 0
    @Nusha: That's incorrect. How did you get that?2011-10-20