Главная > Математика > Конкретная математика. Основание информатики
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

6.4 ГАРМОНИЧЕСКОЕ СУММИРОВАНИЕ

Рассмотрим теперь те суммы, которые содержат гармонические числа, и начнем с небольшой сводки того, что мы узнали в гл. 2: в (2.36) и (2.57) доказано, что

Давайте дерзнем и возьмемся за более общую сумму, которая включает обе эти суммы в качестве частных случаев. Какова величина суммы

когда — целое неотрицательное число?

Метод, который лучше всего подходил для вычисления (6.67) и (6.68) в гл. 2, назывался суммированием по частям. Мы записывали общий член суммы в виде и применяли общее правило

Вспомнили? Сумма которая теперь перед нами, также подходит для этого метода, поскольку можно положить

(Другими словами, гармонические числа имеют простую а биномиальные коэффициенты — простую так что мы на верном пути.) Подстановка этого в (6.69) дает

А оставшаяся сумма вычисляется, поскольку можно внести под знак биномиального коэффициента, полагаясь на наше старое проверенное равенство (5.5):

аким образом, требуемый ответ таков:

(Это чудесно согласуется с (6.67) и (6.68) при

В следующем примере вместо умножения фигурирует деление — попробуем вычислить сумму

Если представить по определению в виде суммы, то мы получим двойную сумму

Но теперь нас выручает другой метод из гл. 2: равенство (2.33) подсказывает, что

Оказывается, что этот ответ можно было бы получить иначе, если бы мы прибегли к суммированию по частям (см. упр. 26).

Теперь испытаем свои силы на более трудной задаче [304], которая не поддается суммированию по частям:

(В этой сумме и намека нет на гармонические числа, но кто знает, вдруг они появятся потом?)

Мы решим эту задачу двумя способами: в одном случае — с трудом вымучивая ответ, а в другом — полагаясь на смекалку и/или везение. Сперва мучительный способ. Разложим по формуле бинома с тем, чтобы объединить мешающее нам к в знаменателе с числителем:

Не такая уж это путаница, как может показаться, ибо во внутренней сумме является многочленом по к, а равенство (5.40) подсказывает, что мы просто берем разность этого многочлена. Так-то оно так, да не совсем — сначала нам нужно внести ясность в ряд деталей. Прежде всего, не является многочленом при это вынуждает нас выделить сей член и иметь с ним дело отдельно. Кроме того, нам не хватает члена при из формулы для разности; поскольку он отличен от нуля при то его следует восстановить (и тут же его снова вычесть). В результате имеем

О’кей, теперь верхняя строка (единственная, в которой осталась двойная сумма) есть нуль: это сумма величин, кратных разностям многочленов степени меньшей а такие разности равны нулю. И вторая строка есть нуль за исключением случая когда она равняется Так что единственное оставшееся затруднение — это третья строка, но зато исходная задача свелась к значительно более простой сумме:

К примеру, следовательно, как и требовалось.

Но как же вычислить Один способ — заменить на получая простую рекуррентную зависимость от Однако имеется более поучительный способ: в (5.41) была получена похожая формула, а именно:

Если избавится от члена при и положить то получим Давайте так и поступим:

(Здесь использовано разложение выражения а в числителе можно выделить х потому, что Из (6.58) нам известно, что следовательно, и получаем такой ответ:

Это один подход. Другой подход — попробовать вычислить значительно более общую сумму

величина исходной суммы будет тогда представлять ее частный случай (К приданию большей общности нас толкает то, что предыдущий вывод „проигнорировал" большую часть

деталей данной задачи — так или иначе те детали не должны иметь отношения к делу, ибо разность ликвидирует их.)

Можно было бы с небольшими изменениями воспроизвести предыдущий вывод и выяснить величину Или можно было бы заменить на а затем заменить на что приводит к рекуррентности

которая благополучно решается с помощью суммирующего множителя (упр. 5).

Но проще всего воспользоваться другим приемом, который сослужил нам добрую службу в гл. 2, - дифференцированием. Производная по у привносит к, которое сокращается с к в знаменателе, в результате чего получается тривиальная сумма:

(Снова разность многочлена степени обратилась в нуль.)

Нами установлено, что производная от по у есть независимо от у. В общем случае, если то поэтому должно быть

Остается определить Но - это просто умноженное на сумму которую мы уже рассмотрели в (6.72); поэтому общая сумма (6.74) выражается в замкнутой форме:

Ну, а в частности, решение исходной задачи — это

<< Предыдущий параграф Следующий параграф >>
Оглавление