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
    @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
    @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
    @Nusha: That's incorrect. How did you get that?2011-10-20