2.3 ПРЕОБРАЗОВАНИЕ СУММ

Ключ к успеху при суммировании лежит в нашей способности преобразовывать одну сумму в другую — либо упрощающую исходную, либо приближающую нас к цели. А выучив несколько основных правил преобразования и поупражнявшись в их применении, можно легко овладеть такой способностью.

Пусть К — некоторое конечное множество целых чисел. Суммы по элементам из К можно преобразовывать, исходя из трех простых правил:

Распределительный закон разрешает вводить и выводить постоянные под знак и за знак . Сочетательный закон позволяет разбивать одну сумму на две или объединять две суммы в одну. Переместительный закон гласит, что члены суммы можно переставлять в любом требуемом порядке; здесь — некоторая перестановка множества всех целых чисел. Например, если и если то три этих закона утверждают соответственно, что

Уловку Гаусса из гл. 1 можно рассматривать как одно из применений этих трех основных законов. Предположим, мы хотим

вычислить сумму арифметической прогрессии общего вида

Согласно переместительному закону, заменив к на получим

Два этих уравнения можно сложить, используя сочетательный закон:

А теперь применим распределительный закон и вычислим тривиальную сумму:

Разделив на 2, выясняем, что

Правую часть можно запомнить как среднее первого и последнего членов, а именно как помноженное на число членов, т. е. на

Важно иметь в виду, что функция в общей форме переместительного закона (2.17) считается перестановкой всех целых чисел. Другими словами, для каждого целого должно существовать в точности одно целое к, такое, что . В противном случае переместительный закон может и не выполняться — упр. 3 тому наглядный пример. Преобразования типа с или где с — целая константа, всегда представляют собой перестановки, поэтому с ними все в порядке.

Впрочем, можно слегка ослабить ограничение на перестановку: достаточно всего лишь, чтобы существовало в точности одно целое к, такое, что когда — элемент индексного множества К. Если (т. е. если не принадлежит К), то не существенно, как часто имеет место равенство поскольку подобное к не участвует в сумме. Так, к примеру, можно утверждать, что

ибо имеется в точности одно к, такое, что когда — четное.

Нотация Айверсона, позволяющая получать 0 или 1 в качестве значений логических выражений внутри некоторой формулы, может быть использована вкупе с распределительным, сочетательным и переместительным законами для выявления дополнительных свойств сумм. Вот, к примеру, важное правило объединения различных множеств индексов: если — некоторые множества целых чисел, то

Это вытекает из общих формул

и

Обычно используется правило (2.20) либо для объединения двух почти непересекающихся индексных множеств, как в случае

либо для выделения отдельного члена суммы, как в случае

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

(Обозначай и властвуй.) Затем мы переписываем двумя способами, выделяя как последний, так и первый члены:

Теперь можно заняться последней суммой и попытаться выразить ее через Если попытка окажется удачной, мы получим уравнение, решением которого и будет искомая сумма.

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

В соответствии с общей схемой приведения (2.24) сумма переписывается в виде

а сумма в правой части равняется распределительному закону. Таким образом, и, разрешая это уравнение относительно получаем

(При х = 1 данная сумма, разумеется, равна просто Правую часть этой формулы можно запомнить как разность первого входящего и первого не входящего в сумму членов, деленную на разность 1 и знаменателя прогрессии.

Все это было довольно простым делом, поэтому давайтека испытаем метод приведения на несколько более трудной сумме,

В данном случае мы имеем но какова же общая формула? В соответствии с (2.24) получаем

так что желательно выразить сумму в правой части через Ну, а ее можно разбить на две суммы с помощью сочетательного закона

и первая из полученных сумм равна . Вторая сумма — это сумма геометрической прогрессии, равная по формуле (2.25). Следовательно, и после алгебраических преобразований получаем

Теперь понятно, почему — это а не

Аналогичный вывод с х вместо 2 привел бы нас к уравнению откуда можно заключить, что

Интересно отметить, что эту замкнутую форму можно было бы вывести совсем другим способом, используя элементарные приемы дифференциального исчисления. Если начать с равенства

и взять производную по х от обеих частей, то получим

поскольку производная суммы равна сумме производных ее слагаемых. В последующих главах мы обнаружим гораздо больше связей между непрерывной и дискретной математикой.