2.4 КРАТНЫЕ СУММЫ

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

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

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

Впрочем, случается использовать и две сигмы, когда речь идет о сумме сумм. Например,

— это сокращенная запись суммы

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

Это обстоятельство представляет собой важное правило, называемое изменением порядка суммирования и обобщающее сочетательный закон (2.16), с которым мы уже знакомы:

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

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

Здесь в первой строке записана сумма из девяти членов безотносительно их порядка. Во второй строке эти члены сгруппированы по три, . В третьей строке используется распределительный закон для вынесения за скобки всех -членов, поскольку и не зависят от к; это дает Четвертая строка аналогична третьей, но с дополнительной парой скобок, введенных с тем, чтобы следующая строка не выглядела слишком загадочной. В пятой строке выносится множитель который встречается при каждом Последняя строка — всего-навсего другая форма записи предыдущей. Подобный вывод можно использовать для доказательства общего распределительного закона

справедливого для всех множеств индексов и К.

Основное правило (2.27) изменения порядка суммирования допускает разного рода вариации, возникающие, когда мы хотим ограничить области изменения индексов вместо суммирования по всем целым и к. Эти вариации вызывают два ощущения: ванили и булыжной мостовой. Сперва — „ванильная" версия:

Это всего лишь другой способ записи (2.27), поскольку скобки Айверсона распадаются в произведение скобок . Правило с привкусом ванили применимо во всех случаях, когда области изменения и к не зависят друг от друга.

„Булыжная" формула изменения порядка суммирования несколько более мудреная. Она применима, когда область изменения индекса внутренней суммы зависит от переменного индекса внешней суммы:

В этом случае множества должны быть связаны так, чтобы

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

Это равенство по Айверсону делает справедливой следующую запись:

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

Используем эти соображения с пользой для дела. Рассмотрим матрицу

из произведений Наша цель — найти простую формулу для

суммы всех элементов на и над главной диагональю этой матрицы. Поскольку матрица симметрична относительно главной диагонали; следовательно, будет приближенно равно полусумме всех элементов (за исключением лишнего члена, отвечающего главной диагонали).

Подобные наводящие соображения служат поводом для следующих манипуляций:

поскольку можно переобозначить как Кроме того, поскольку

мы получаем

Первая сумма по общему распределительному закону (2.28) есть а вторая — . Поэтому

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

Воодушевленные таким успехом, рассмотрим еще одну двойную сумму:

Здесь мы снова имеем симметрию относительно перестановки :

Поэтому сумму можно сложить саму с собой, используя соотношение

с тем, чтобы заключить, что

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

На последнем шаге обе суммы подверглись упрощению в соответствии с общим распределительным законом (2.28). Если же

преобразование первой суммы остается загадкой — воспроизведем его не спеша снова:

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

Возвращаясь к тому месту, где мы остановились, теперь можно поделить все пополам, произвести перестановку и получить интересную формулу:

В качестве частных случаев это соотношение дает неравенства Чебышева для сумм:

если

если

(В общем случае, если и если — некоторая перестановка множества то нетрудно доказать, что наибольшее значение достигается при а наименьшее значение — при

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

если является некоторой перестановкой целых чисел. Но что будет, если заменить к на , где — произвольная функция

которая переводит целое в целое ? Общая формула замены переменной выглядит так:

где обозначает число элементов множества

т. е. число элементов таких, что равно к.

Формулу (2.35) легко доказать, изменив порядок суммирования:

поскольку частном случае, когда — взаимно однозначное соответствие между и К, имеем при всех к, и общая формула (2.35) сводится к формуле

Это переместительный закон (2.17), с которым мы уже имели дело — в слегка замаскированном виде.

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

В частности,

Обычный способ вычисления двойной суммы состоит в суммировании сначала по или же сначала по к — поэтому давайте испробуем обе возможности.

Увы! Мы не знаем, как загнать сумму гармонических чисел в замкнутую форму.

Если же попробовать начать суммировать по-другому, то получим

И вновь оказываемся в том же самом тупике.

Но имеется еще один путь, по которому можно добраться до цели, если заменить на прежде чем решиться на сведение к сумме сумм:

Ура! Мы нашли . Сопоставляя результаты этого „забега" с допущенными фальстартами, мы получаем в качестве приза следующее соотношение:

Использованную здесь уловку можно осмыслить двояко: во-первых, алгебраически, а во-вторых, геометрически. (1) Алгебраически: если дана двойная сумма, члены которой включают в себя где — произвольная функция, то этот пример показывает, что неплохо попробовать заменить к на и просуммировать по Геометрически: можно представить сумму например сумму при в следующем виде:

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