Этот приём позволяет просуммировать ряд

п-1 1

По-

к=1 к(к+1) -

скольку -щщ = \ - получаем, что

п-1

1

1

П

к(к + 1)

k=i

Произведения

Произведение чисел а\

а г, записывают как

п

к=1

При п = 0 значение (1е&произведения (product) считается равным 1. Логарифмирование превращает произведение в сумму:

Упражнения

ЗЛ-1 Вычислите 22=1(2к - 1).

ЗЛ-2* Покажите, используя формулу для частичных сумм гармонического ряда, что Ук=1- 1) = 1п(д/п) + 0(1).

3.1-3* Покажите, что J2T=o(k ~ 1)/2к = °-

3.1-4* Вычислите сумму J2T=i(2k + 1)х<2к

ЗЛ-5 Используя линейность суммы, сформулируйте и докажите утверждение о возможности перестановки асимптотического О-обозначения и суммирования.

3.1-6 Используя линейность суммы, сформулируйте и докажите утверждение о возможности перестановки асимптотического Q-обозначения и суммирования.

3.1-7 Вычислите произведение П/с=1 2 • 4fc.

3.1-8* Вычислите произведение П/с=2(1 - V2)-

п

п

к=1

к=1

3.2. Оценки сумм

Рассмотрим несколько приёмов, которые позволяют найти значение суммы (или хотя бы оценить эту сумму сверху или снизу).

Индукция

Если удалось угадать формулу для суммы, её легко проверить с помощью математической индукции. Пример: докажем, что сумма арифметической прогрессии Sn = Ук=1 к равна га(га+1)/2. При га = 1 это верно. Теперь предположим, что равенство Sn = п(п + 1)/2 верно при некотором га и проверим его для га + 1. В самом деле,

п+1п

к = к + (п+1) = п(п + 1)/2 + (га + 1) = (га + 1)(га+ 2)/2.

к=1к=1

Индукцию можно использовать и для неравенств. Например, покажем, что сумма геометрической прогрессии Yk=o к есть О (3й). Точнее, мы покажем, что fc=o к с-3й для некоторой константы с (которую мы выберем позднее). При га = 0 имеем 1=о 3fc = 1 с • 1; это верно при с 1. Предполагая справедливость оценки при некотором га, докажем её для га + 1. Имеем:

п+1п/11\

£3fc = 3fc + 3n+1 сТ + 3n+1 = I - + - J c3n+1 c3n+1. к=о к=о С

Последний переход законен, если (1/3+ 1/с) 1, т.е. если с 3/2. Поэтому ££=03* = 0{Т), что и требовалось доказать.

Индукцией следует пользоваться аккуратно, особенно при доказательстве асимптотических оценок, поскольку тут легко ошибиться. Для примера «докажем», что $=1 к = О(п). Очевидно, 2\=1к = 0(1). Предполагая справедливость оценки при некотором га, докажем её для следующего значения га. В самом деле,

п-\-1п

J2k = J2k + (n+l) = 0(n) + (n + l) [не=РНо!] О (п + 1).

к=1к=1

Ошибка в том, что константа, подразумеваемая в обозначении О (га), растёт вместе с га.

Почленные сравнения

Иногда можно получить верхнюю оценку для суммы, заменив каждый её член на больший (например, на наибольший из членов

суммы). Так, простейшей оценкой сверху для суммы арифметической прогрессии Ук=1 к будет

В общем случае

к=1к=1

Е-

га = га2.

ак гаап fc=i

где атах - наибольшее из а\,..., ап.

В некоторых случаях можно применить более точный метод - сравнение с геометрической прогрессией. Допустим, дан ряд ~Yk=Qak с положительными членами, для которого axja г при всех к 0 и некотором г < 1. Тогда aoj и сумма может быть ограничена сверху бесконечной убывающей геометрической прогрессией:

поооо

ак a0rfc = а0 rfc = aoy--

к=0к=0к=0

Применим этот метод для суммы Yh=i к%~к Первый член равен 1/3, отношение соседних членов равно

(к+ l)3"(fc+1) 1 к + 1 2 ЛЗ1-* ~ 3 к 3

для всех к 1. Следовательно, каждый член суммы оценивается сверху величиной (l/3)(2/3)fc, так что

оо

к=1к=1 " V"7" " 3

Важно, что отношение соседних членов не просто меньше 1, а ограничено некоторой константой г < 1, общей для всех членов ряда. Например, для гармонического ряда отношение (к + 1)-го и к-го членов равно -щ-г < 1. Тем не менее

оо п 1

Игл У - = lim O(lgra) = 00.

- к п->оо - к п->оо

fc=lfc=l

Здесь не существует константы г, отделяющей отношения соседних членов от единицы.