Asymptotic analysis question: sum[log(i)*i^3, {i, n}] is big-theta (log(n)*n^4)

Question

I've got a homework question that's been puzzling me. It asks that you prove that the function Sum[log(i)*i^3, {i, n}) (ie. the sum of log(i)*i^3 from i=1 to n) is big-theta (log(n)*n^4).

I know that Sum[i^3, {i, n}] is ( (n(n+1))/2 )^2 and that Sum[log(i), {i, n}) is log(n!), but I'm not sure if 1) I can treat these two separately since they're part of the same product inside the sum, and 2) how to start getting this into a form that will help me with the proof.

Any help would be really appreciated. Thanks!

Answer 1

The series looks like this - log 1 + log 2 * 2^3 + log 3 * 3^3....(upto n terms) the sum of which does not converge. So if we integrate it

Integral to (1 to infinity) [ logn * n^3] (integration by parts)

you will get 1/4*logn * n^4 - 1/16* (n^4)

It is clear that the dominating term there is logn*n^4, therefore it belongs to Big Theta(log n * n^4)

The other way you could look at it is -

The series looks like log 1 + log2 * 8 + log 3 * 27......+ log n * n^3. You could think of log n as the term with the highest value, since all logarithmic functions grow at the same rate asymptotically,

You could treat the above series as log n (1 + 2^3 + 3^3...) which is

log n [n^2 ( n + 1)^2]/4

Assuming f(n) = log n * n^4 g(n) = log n [n^2 ( n + 1)^2]/4

You could show that lim (n tends to inf) for f(n)/g(n) will be a constant [applying L'Hopital's rule]

That's another way to prove that the function g(n) belongs to Big Theta (f(n)).

Hope that helps.

Answer 2

Hint for one part of your solution: how large is the sum of the last two summands of your left sum?

Hint for the second part: If you divide your left side (the sum) by the right side, how many summands to you get? How large is the largest one?

Hint for the first part again: Find a simple lower estimate for the sum from n/2 to n in your first expression.

Answer 3

Try BigO limit definition and use calculus.

For calculus you might like to use some Computer Algebra System.

In following answer, I've shown, how to do this with Maxima Opensource CAS : Asymptotic Complexity of Logarithms and Powers