2. Исчисление сумм

СУММЫ ВЕЗДЕСУЩИ в математике, поэтому нам потребуются основные приемы обращения с ними. Эта глава знакомит с теми обозначениями и методами, которые помогут освоиться с суммированием.

2.1 ОБОЗНАЧЕНИЯ СУММ

В гл. 1 мы уже сталкивались с суммой первых натуральных чисел, которую старательно выписывали как

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

С другой стороны, включение членов 3 и было излишней

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

Мы будем иметь дело с суммами общего вида

где каждое — определенное каким-то образом число. Такое обозначение имеет то преимущество, что при наличии достаточно богатого воображения можно „представить" себе всю сумму целиком, почти так, как если бы она была выписана полностью.

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

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

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

которая называется сигма-обозначением, поскольку здесь фигурирует греческая буква (прописная сигма). Это обозначение говорит, что включать в сумму надо именно те члены номер к которых является целым числом, лежащим между нижней и верхней границами 1 и включительно. Это произносится как „сумма по к от 1 до Это - обозначение ввел Жозеф Фурье в 1820 г., и оно вскоре покорило математический мир.

Кстати, величина после знака (в данном случае называется общим членом.

Говорят, что переменный индекс к связан знаком в (2.2), поскольку к в не имеет отношения к тем к, которые появляются за рамками сигма-обозначения. В частности, любая другая буква могла бы заменить к без изменения смысла (2.2). Часто используется буква (возможно потому, что с нее начинается слово «indех»), но мы будем, как правило, суммировать по к, поскольку разумно сохранить i за

Оказывается, что еще более полезным, чем форма записи с явными пределами, является обобщенное сигма-обозначение: мы просто записываем одно или несколько условий под знаком задавая тем самым множество значений индекса, по которым следует проводить суммирование. Например, суммы (2.1) и (2.2) можно записать иначе как

Хотя в этом отвлеченном примере и не видно существенного различия между новым обозначением и обозначением (2.2), обобщенное обозначение позволяет «брать» суммы по множествам значений индекса, не ограниченным последовательными целыми числами. К примеру, сумму квадратов всех нечетных положительных чисел, меньших 100, можно выразить таким образом:

Аналог этой суммы с явными пределами

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

в случае формы записи с явными пределами потребовалось бы написать

где означает простое число, — количество простых чисел, не превосходящих (Между прочим, эта сумма дает приблизительно среднее число простых делителей „случайного" целого числа, близкого к поскольку около этих целых чисел делятся на . При большом она примерно равна ., где -константа Мертенса [220], означает натуральный логарифм х, а означает

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

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

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

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

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

Формально

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

Если знак суммы появляется в тексте, а не в выделенной формуле, то используется слегка измененная форма записи (2.4): мы пишем придавая условию вид нижнего индекса при того чтобы формула не слишком выходила за пределы строки. Аналогично, представляет собой удобный вариант записи (2.2), если мы хотим уместить данное обозначение в одну строку.

Зачастую соблазнительна запись

поскольку при соответствующие члены этой суммы равны нулю — разве не разумнее сложить члена вместо членов? Но не надо поддаваться таким соблазнам: разумность в смысле вычисления и разумность в смысле понимания — это не одно и то же! В дальнейшем мы обнаружим, что как можно более простые верхние и нижние границы индекса суммирования имеют то преимущество, что при простых границах гораздо проще обращаться с суммами. Более того, обозначение типа может даже приводить к опасной двусмысленности, поскольку не совсем ясен его смысл при или (см. упр. 1). Нулевые члены безопасны и часто избавляют от ненужных хлопот.

Обозначения, которые мы обсуждали до сих пор, являются общепринятыми, но сейчас мы собираемся решительно отступить от сложившейся традиции. Кеннет Айверсон в своем языке программирования АПЛ [4, с. 11, см. также 152], внес замечательную идею, которая, как будет видно, существенно упрощает многое из того, что мы собираемся проделать в этой книге. Его идея состоит в том, чтобы просто заключать истинное-или-ложное утверждение в квадратные скобки и считать при этом, что результат равен 1, если данное утверждение истинно, и 0, если данное утверждение ложно. Например,

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

Если ложно, то член равен нулю, так что можно спокойно включать его в состав суммируемых членов. Это упрощает манипулирование с индексом суммирования, ибо нет нужды беспокоиться о граничных условиях.

Необходимо только отметить одну техническую деталь: иногда бывает определено не для всех целых k. Это затруднение можно обойти, допуская, что является „очень сильно нулевым", когда ложно, — оно настолько нулевое, что делает равным нулю, даже когда не определено. Например, если воспользоваться нотацией Айверсона для записи суммы чисел, обратных простым в виде

то при , равном нулю, проблем с делением на нуль не возникает, потому что наше допущение позволяет считать, что [О простое] .

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