Is the Summation of lg k in log(n!) Equal to Theta (n lgn)?

[MzLeeTooFresh]

Homework Statement

Prove that the following is true:
n
$$\Sigma$$ lg k = $$\Theta$$ (n lgn)
k=1

Homework Equations

the lg in this case is base 2

The Attempt at a Solution

i don't kno how to apply geometric or arithmetic progression to the 1st part
i was trying to substitute for k but that wasnt working out.
i'm not looking for the answer but for some guidance as to how to deal with the summation

 

[HallsofIvy]

it helps a lot to know that log(a)+ log(b)= log(ab)!

There is NO artihmetic or geometric progression here.

 

[atomthick]

Sum(lg k) = lg (n!)

we have n! < nⁿ therefore

Sum(lg k) = lg (n!) < lg (nⁿ) = nlg(n)

 

[MzLeeTooFresh]

so it would then be:
n
lg $$\Pi$$ k
k=1
?

 

[atomthick]

yes, just like HallsofIvy suggested lg 1 + lg 2 + ... + lg (n) = lg 1*2*3...*n = lg (n!)

 

[MzLeeTooFresh]

ok thank you

 

[dextercioby]

What's that $\Theta$ ?

 

[Robert1986]

ok thank you

Two things, another, equivelant way to look at it is this:

The biggest term in: Sum(log k) is log n, since there are n terms, sum(log k) < n log n

Second, all you have shown is that sum(log k) = O(n log n), but you need to show it is BigTheta.

 

[Robert1986]

That is, you need to find an absolute constant K and an N(K) such that if n > N(K) then K n log n < log(n!).