Пример 4 {Сумма арифметической прогрессии). Предположим, что п > 0. Тогда а + [а+Ъ) + • • • + (а + пЬ)

= (а + bj) по определению (2)

0<j<n

= Е {а + Ь{п~ j)) по правилу (Ь)

0<n-j<n

= (а + Ьп - bj) в результате упрощения

0<j<n

= (2а + 6п) - Е (° - согласно (8)

0<j<n 0<j<n

= (n + 1)(2а + bn) - (а + bj),

o<i<n

так как первая сумма - это просто (п + 1) одинаковых слагаемых, не зависящих от j. Теперь, приравнивая первое и последнее выражения и деля их на 2, получаем

(a + bj) = a(n + l) + ibn(n + l). (15)

А это равно п + 1, умноженному на (а + (а + Ьп)), что можно интерпретировать как количество слагаемых, умноженное на среднее первого и последнего слагаемых.

Итак, выполняя только простые операции над суммами, мы получили важные соотношения (13)-(15). В большинстве учебников эти формулы просто приводятся, а затем доказываются по индукции. Индукция - это, конечно, идеальный способ доказательства, но он не дает никакого объяснения по поводу того, каким же образом кому-то удалось придумать саму формулу, если исключить возможность некоего внезапного озарения. Занимаясь анализом алгоритмов, мы будем сталкиваться с сотнями сумм, которые не соответствуют ни одному из известных образцов. Но, выполняя над этими суммами приведенные выше операции, мы во многих случаях сможем найти решение и без догадок.

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

г , Г1, если утверждение истинно;

утверждение = < „ j /щ

10, если утверждение ложно.

Например, можно записать

R(3) j

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

Пользуясь введенным обозначением, можно оригинальным способом вывести правило (Ь) из правил (а) и («):

Е "рЬ) = J2 Ыз) [RiPiJ)).

j i

= J2ai[R{i)]J2[i=pU)]- (18)

Сумма по j равна 1, когда R{i) истинно, если предположить, что р - это перестановка в области суммирования, как требуется в (5); таким образом, остается сумма J2 ai[R{i)], которую можно записать как YlR{i) <г- Соотношение (5) доказано. Если же р не является перестановкой в области суммирования, то значение суммы Y1r(p(j)) p(j) вьфажается формулой (18).

Самым известным частным случаем обозначения (16) является так называемый символ Кронекера,

: г- -1 f 1> еслиг=7, = = [о, еслиМ,-,

введенный Леопольдом Кронекером (Leopold Кгопескег) в 1868 году. Более обшде обозначения типа (16) были введены К. Ю. Айверсоном (К. Е. Iverson) в 1962 году, поэтому (16) часто называют обозначением Айверсона. [См. D. Е. Knuth, AMM 99 (1992), 403-422.]

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

П «г (20)

Так обозначается произведение всех а, для которых целое число j удовлетворяет соотношению R{j). Если ни одного такого целого j не существует, то по определению произведение равно 1 (а не 0).

Правила (Ь), (с) и (d) справедливы для произведений fl так же, как и для сумм Yl> если внести в них необходимые коррективы. Несколько примеров, в которых необходимо выполнить операции над произведениями, приводится в упражнениях (они даны в конце раздела).

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

Е Е °У = Е Е Е = Е

0<i<n 0<j<n 0<t,j<n 0<г<п 0<j<i 0<j<i<n.

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

п i

Е E°j- = Е < i < <i <= Е < <

t=l j=l i,j ij

n n

= EE°>>

j=i i=j

воспользовавшись тем, что [1 < г < n][l < j < г] = [1 < j < г < n] = [1 < j < n][j < г < п]. Аналогично более общая форма соотношения (9) следует из тождества

[Rii)][Sii,j)] = [Rii) и S(i,j)] = [SiJ)][Rii,j)] (21)

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

Е «л...in- (22)

Л> •>j»>o

Здесь переменная а имеет п подстрочных индексов, например для п = 5 это выражение примет следующий вид:

«11111 + «21110 + «22100 + «31100 + «32000 + «41000 + «50000-

(См. замечания о разбиении числа в разделе 1.2.1.)

УПРАЖНЕНИЯ (часть 1)

1. [01] Что означает запись ]d<j<n j ЛЛ" - 3.14?

2. [10] Не пользуясь знаком суммы запишите эквивалент выражения

Е 2п + 1

0<п<5

а также выражения

2п2 -Ы

0<п2<5

► 3. [IS] Объясните, почему несмотря на правило (Ь) результаты предыдущего упражнения различны.

4. [10] Не пользуясь знаком запишите эквиваленты каждой части равенства (10) как суммы сумм для случая п = 3.

5. [НМ20] Докажите, что правило (а) справедливо для произвольного бесконечного ряда при условии, что этот ряд сходится.

6. [НМ20] Докажите, что правило (d) справедливо для произвольного бесконечного ряда при условии, что сходятся любые три суммы из четырех.

7. [HM2S] Покажите, что если с-любое целое число, то Yru) - Yslc-j) c-j, даже если оба ряда бесконечны.

8. [НМ25] Приведите пример бесконечного ряда, для которого равенство (7) ложно.

9. [05] Справедливо ли доказательство формулы (14) для n =-1? 10. [05] Справедливо ли доказательство формулы (14) для п - -2?