Вопрос об асимптотическом анализе: сумма [log (i) * i ^ 3, {i, n}] является бета-тета (log (n) * n ^ 4)

Question

У меня вопрос к домашней задаче, который меня озадачивал.Он просит вас доказать, что функция Sum [log (i) * i ^ 3, {i, n}) (т. Е. Сумма log (i) * i ^ 3 от i = 1 до n) является бета-тета(log (n) * n ^ 4).

Я знаю, что Sum [i ^ 3, {i, n}] есть ((n (n + 1)) / 2) ^ 2 и что Sum[log (i), {i, n}) - это log (n!), но я не уверен, что 1) я могу рассматривать эти два по отдельности, так как они являются частью одного и того же продукта в сумме, и 2)как начать получать это в форме, которая поможет мне с доказательством.

Любая помощь будет очень признательна.Спасибо!

Answer 1

Серия выглядит следующим образом - log 1 + log 2 * 2 ^ 3 + log 3 * 3 ^ 3 .... (до n терминов) сумма которых не сходится. Так что, если мы интегрируем это

Интегрально в (от 1 до бесконечности) [logn * n ^ 3] (интеграция по частям)

вы получите 1/4 * logn * n ^ 4 - 1/16 * (n ^ 4)

Понятно, что доминирующим термином здесь является logn * n ^ 4, поэтому он принадлежит Большой Тэте (log n * n ^ 4)

Другой способ взглянуть на это -

Серия выглядит как log 1 + log2 * 8 + log 3 * 27 ...... + log n * n ^ 3. Вы можете думать о log n как о члене с наибольшим значением, поскольку все логарифмические функции растут с одинаковой скоростью асимптотически,

Вы можете рассматривать вышеупомянутую серию как 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

Вы можете показать, что lim (n стремится к inf) для f (n) / g (n) будет константой [применяя правило Л'Опитала]

Это еще один способ доказать, что функция g (n) принадлежит Большой тэте (f (n)).

Надеюсь, это поможет.

Answer 2

Подсказка для одной части вашего решения: насколько велика сумма двух последних слагаемых вашей левой суммы?

Подсказка для второй части: если вы разделите левую сторону(сумма) справа, сколько слагаемых вам достанется?Насколько велик самый большой?

Подсказка для первой части: найдите простую нижнюю оценку суммы от n / 2 до n в вашем первом выражении.

Answer 3

Попробуйте определение предела BigO и используйте исчисление.

Для исчисления вы можете использовать систему компьютерной алгебры.

В следующем ответе я показал, как это сделать с помощью Maxima Opensource CAS: Асимптотическая сложность логарифмов и степеней