渐近分析问题: sum[log(i)*i^3，{i，n}]是big-theta (log(n)*n^4)

Question

我有一个家庭作业的问题一直困扰着我。它要求你证明函数Sum[log(i)*i^3，{i，n}) (即.log(i)*i^3从i=1到n)的和是大θ(log(n)*n^4)。

我知道Sumi^3，{i，n}是((n(n+1))log )^2，sum [/2(I)，{i，n})是log(n!)，但我不确定1)我是否可以单独对待这两个，因为它们是sum中相同乘积的一部分，以及2)如何开始将其转化为一种有助于证明的形式。

任何帮助都将不胜感激。谢谢!

Answer 1

级数看起来是这样的-log1+log2* 2^3 +log3*3^3...(最多n项)，它们的和不收敛。所以如果我们把它整合起来

对(1到无穷大) logn * n^3的整数

您将得到1/4*logn * n^4 - 1/16* (n^4)

很明显，那里的主导项是logn*n^4，因此它属于Big Theta(log n* n^4)。

你可以从另一个角度看这件事-

该级数看起来像log1+log8+log3* 27......+ log * n^3。你可以认为log是具有最高值的项，因为所有对数函数都以相同的速率渐近增长，

您可以将上述级数视为log n (1 + 2^3 + 3^3...)这就是

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

假设f(n) = log n* n^4 g(n) = log n n^2 (n+ 1)^2/4

你可以证明对于f (n )，/g(N)是一个常数，应用L‘’Hopital规则

这是证明函数g(n)属于Big Theta (f(n))的另一种方法。

希望这能有所帮助。

Answer 2

尝试使用BigO限制定义并使用微积分。

对于微积分，你可能喜欢使用一些计算机代数系统。

在下面的回答中，我展示了如何使用Maxima Opensource CAS实现这一点：Asymptotic Complexity of Logarithms and Powers