Суммы и ряды

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

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

Сумму nn первых натуральных чисел можно записать как 1+2+3+⋯+(n−1)+n1 + 2 + 3 + \dotsb + (n-1) + n. Многоточие здесь указывает на то, что я пропустил несколько членов, и их нужно восстановить по какой-то общей закономерности. С тем же успехом можно записать и сумму 2+4+6+⋯+2n2 + 4 + 6 + \dotsb + 2n. Но, например, если я запишу 1+7+14.2+⋯+78.591 + 7 + 14.2 + \dotsb + 78.59, то меня никто не поймет. Так что при использовании троеточия закономерность должна быть понятна. Также должно быть очевидно количество членов в сумме.

Например, сумма 1+2+⋯+2n1 + 2 + \dotsb + 2^n может читаться двояко: в этой сумме 2n2^n чисел или только n−1n-1? Если подразумевается первый вариант, то лучше расписать ещё несколько членов: 1+2+3+⋯+(2n−1)+2n1 + 2 + 3 + \dotsb + (2^n-1) + 2^n. А если подразумевается второй вариант, то лучше явно выделить закономерность, написав 20+21+⋯+2n2^0 + 2^1 + \dotsb + 2^n.

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

Пусть a1,a2,…,ana_1, a_2, \dotsc, a_n — произвольный набор чисел. Мы будем иметь дело с суммами вида a1+a2+⋯+ana_1 + a_2 + \dotsb + a_n. Такую сумму более компактно можно записать как

∑j=1naj   ⁣=def   ⁣a1+a2+a3+⋯+an−1+an\sum\limits_{j=1}^n a_j \defeq a_1 + a_2 + a_3 + \dotsb + a_{n-1} + a_n

Эта запись означает суммирование всех aja_j при целых значениях переменной jj от 11 до nn. Если nn равно 00, то и соответствующее значение суммы равно 00.

Границы суммирования можно изменять. То есть можно начать когда угодно и закончить когда угодно:

∑i   ⁣=   ⁣xyai   ⁣=def   ⁣ax+ax+1+ax+2+⋯+ax+y−1+ax+y\sum\limits_{i \;\! = \;\! x}^y a_i \defeq a_x + a_{x+1} + a_{x+2} + \dotsb + a_{x+y-1} + a_{x+y}

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

Пусть R(j)R(j) — любое соотношение (условие), зависящее от jj. Тогда запись

∑R(j)aj\sum\limits_{R(j)} a_j

означает сумму всех aja_j, где jj удовлетворяет соотношению R(j)R(j). Если чисел, удовлетворяющих соотношению нет, то значение такой суммы по определению принимается равным 00.

Например, я хочу суммировать только по простым числам, которые не больше nn. Тогда я ввожу соотношение R(j)R(j), которое означает, что число jj является простым, и при этом j⩽nj \le n. Можно суть соотношения писать прямо в самом обозначении суммирования, и тогда получается какая-то такая конструкция:

∑простое pp⩽n1p=ln⁡ln⁡n+M+o(1)\sum\limits_{\substack{\text{простое}~ p \\ p \;\! \le \;\! n}} \frac{1}{p} = \ln \ln n + M + o(1)

Хотя, всегда можно превратить такую сумму в явную сумму с границами, введя дополнительные обозначения: если pkp_k — kk-ое простое число и π(n)\pi(n) — количество простых чисел, не больших nn, то тогда

∑простое pp⩽n1p=∑k=1π(n)1pk\sum\limits_{\substack{\text{простое}~ p \\ p \;\! \le \;\! n}} \frac{1}{p} = \sum\limits_{k=1}^{\pi(n)} \frac{1}{p_k}

Когда речь заходит о бесконечных суммах, принято в качестве верхней границы писать ∞\oo. То есть

∑i   ⁣=   ⁣0∞ai   ⁣=def   ⁣a0+a1+a2+a3+⋯\sum\limits_{i \;\! = \;\! 0}^\oo a_i \defeq a_0 + a_1 + a_2 + a_3 + \dotsb

Во всех этих обозначениях jj называется индексом или индексной переменной, а aja_j называется суммируемым выражением. Если не сказано иного, индекс считается целым числом. Знак Σ\Sigma — греческая буква сигма, означающая сумму. Впервые все эти обозначения были введены Жан-Батистом Жозефом Фурье в 1820 году.

Правила конечного суммирования

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

Распределительный закон над произведением сумм

(∑R(i)ai)⋅(∑S(j)bj)=∑R(i)∑S(j)aibj\biggl(\sum\limits_{R(i)} a_i\biggr) \cdot \biggl(\sum\limits_{S(j)} b_j\biggr) = \sum\limits_{R(i)} \sum\limits_{S(j)} a_i b_j

Замена индекса суммирования

Пусть p(i)p(i) — функция, задающая перестановку чисел на области суммирования. Точнее, для каждого ii, удовлетворяющего соотношению R(i)R(i), ставится в соответствие число jj такое, что p(j)=ip(j) = i. Тогда

∑R(i)ai=∑R(j)aj=∑R(p(i))ap(i)\sum\limits_{R(i)} a_i = \sum\limits_{R(j)} a_j = \sum\limits_{R(p(i))} a_{p(i)}

Очень частыми заменами являются p(i)=c±ip(i) = c \pm i, где cc — константа, не зависящая от ii. Например

∑i   ⁣=   ⁣1nai=∑1   ⁣⩽   ⁣i⩽nai=∑1   ⁣⩽   ⁣i−1⩽nai−1=∑2   ⁣⩽   ⁣i⩽n+1ai−1=∑i   ⁣=   ⁣2n+1ai−1\sum\limits_{i \;\! = \;\! 1}^n a_i = \sum\limits_{1 \;\! \le \;\! i \le n} a_i = \sum\limits_{1 \;\! \le \;\! i-1 \le n} a_{i-1} = \sum\limits_{2 \;\! \le \;\! i \le n+1} a_{i-1} = \sum\limits_{i \;\! = \;\! 2}^{n+1} a_{i-1}

Изменение порядка суммирования

∑R(i)∑S(j)ai,j=∑S(j)∑R(i)ai,j\sum\limits_{R(i)} \sum\limits_{S(j)} a_{i, \- j} = \sum\limits_{S(j)} \sum\limits_{R(i)} a_{i, \- j}

Порядок суммирования можно изменять даже тогда, когда внутреннее условие SS зависит и от ii, и от jj.

∑R(i)∑S(i,j)ai,j=∑S′(j)  ∑R(i) и S(i,j)ai,j\sum\limits_{R(i)} \sum\limits_{S(i, j)} a_{i, \- j} = \sum\limits_{S'(j)} \; \sum\limits_{R(i) ~\text{и}~ S(i, j)} a_{i, \- j}

Здесь S′(j)S'(j) означает, что существует целое ii такое, что справедливы как R(i)R(i), так и S(i,j)S(i, j).

Например, для суммы ∑i=1n∑j=1iai,j\sum\limits_{i=1}^n \sum\limits_{j=1}^i a_{i, \- j} условие R(i)R(i) означает 1⩽i⩽n1 \le i \le n, а условие S(i,j)S(i, j) означает 1⩽j⩽i1 \le j \le i. После преобразований условие S′(j)S'(j) означает существование целого ii такого, что 1⩽i⩽n1 \le i \le n и 1⩽j⩽i1 \le j \le i, то есть 1⩽j⩽n1 \le j \le n. А условие 1⩽i⩽n1 \le i \le n и 1⩽j⩽i1 \le j \le i превращается в j⩽i⩽nj \le i \le n. В результате получаем

∑i=1n∑j=1iai,j=∑j=1n∑i=jnai,j\sum\limits_{i=1}^n \sum\limits_{j=1}^i a_{i, \- j} = \sum\limits_{j=1}^n \sum\limits_{i=j}^n a_{i, \- j}

Манипуляции с областью суммирования

Пусть R(i)R(i) и S(i)S(i) — произвольные соотношения. Тогда

∑R(i)ai+∑S(i)ai=∑R(i) и S(i)ai  +  ∑R(i) или S(i)ai\sum\limits_{R(i)} a_i + \sum\limits_{S(i)} a_i = \sum\limits_{R(i) ~\text{и}~ S(i)} a_i \;+\; \sum\limits_{R(i) ~\text{или}~ S(i)} a_i

Например, если 1⩽m⩽n1 \le m \le n, то

∑1   ⁣⩽   ⁣i⩽mai+∑m   ⁣⩽   ⁣i⩽nai=am+∑1   ⁣⩽   ⁣i⩽nai\sum\limits_{1 \;\! \le \;\! i \le m} a_i + \sum\limits_{m \;\! \le \;\! i \le n} a_i = a_m + \sum\limits_{1 \;\! \le \;\! i \le n} a_i

В случае, когда суммы бесконечны, эти операции не всегда применимы. Достаточным условием для применения этих операций является абсолютная сходимость интересующего нас ряда. То есть, например, достаточным условием применения любой замены p(i)p(i) к ряду ∑R(i)ai\sum\limits_{R(i)} a_i является сходимость ряда ∑R(i)∣ai∣\sum\limits_{R(i)} |a_i|.

Основные тождества

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

Сумма пар. Рассмотрим такую сумму

S=∑i=0n∑j=0iai ajS = \sum\limits_{i=0}^n \sum\limits_{j=0}^i a_i \, a_j

Поменяв порядок суммирования, получим

S=∑i=0n∑j=0iai aj=∑j=0n∑i=jnai aj=∑i=0n∑j=inai ajS = \sum\limits_{i=0}^n \sum\limits_{j=0}^i a_i \, a_j = \sum\limits_{j=0}^n \sum\limits_{i=j}^n a_i \, a_j = \sum\limits_{i=0}^n \sum\limits_{j=i}^n a_i \, a_j

Теперь мы можем два раза записать исходную сумму, выражая её по-разному

2S=∑i=0n∑j=0iai aj+∑i=0n∑j=inai aj=∑i=0n(∑j=0iai aj+∑j=inai aj)==∑i=0n(∑j=0nai aj+ai2)=∑i=0n∑j=0nai aj+∑i=0nai2==(∑i=0nai)⋅(∑j=0naj)+∑i=0nai2=(∑i=0nai)2+∑i=0nai2\align{ 2S &= \sum\limits_{i=0}^n \sum\limits_{j=0}^i a_i \, a_j + \sum\limits_{i=0}^n \sum\limits_{j=i}^n a_i \, a_j = \sum\limits_{i=0}^n \biggl( \sum\limits_{j=0}^i a_i \, a_j + \sum\limits_{j=i}^n a_i \, a_j \biggr) =\\[0.4em]&= \sum\limits_{i=0}^n \biggl( \sum\limits_{j=0}^n a_i \, a_j + a_i^2 \biggr) = \sum\limits_{i=0}^n \sum\limits_{j=0}^n a_i \, a_j + \sum\limits_{i=0}^n a_i^2 =\\[0.4em]&= \biggl( \sum\limits_{i=0}^n a_i \biggr) \cdot \biggl( \sum\limits_{j=0}^n a_j\biggr) + \sum\limits_{i=0}^n a_i^2 = \biggl( \sum\limits_{i=0}^n a_i \biggr)^2 + \sum\limits_{i=0}^n a_i^2 }

В итоге мы получили формулу

∑i=0n∑j=0iai aj=12⋅((∑i=0nai)2+∑i=0nai2)\sum\limits_{i=0}^n \sum\limits_{j=0}^i a_i \, a_j = \frac{1}{2} \cdot \Biggl( \biggl( \sum\limits_{i=0}^n a_i \biggr)^2 + \sum\limits_{i=0}^n a_i^2 \Biggr)

Геометрическая прогрессия. Давайте вычислим сумму геометрической прогрессии.

∑j=0na xj=a+∑j=1na xj=a+x⋅∑j=1na xj−1==a+x⋅∑j=0n−1a xj=a+x⋅∑j=0na xj−a xn+1\align{ \sum\limits_{j=0}^n a \, x^j &= a + \sum\limits_{j=1}^n a \, x^j = a + x \cdot \sum\limits_{j=1}^n a \, x^{j-1} =\\[0.4em]&= a + x \cdot \sum\limits_{j=0}^{n-1} a \, x^j = a + x \cdot \sum\limits_{j=0}^n a \, x^j - a \, x^{n+1} }

Теперь, сравнивая первое и последнее выражения, получаем

(1−x)⋅∑j=0na xj=a−a xn+1(1-x) \cdot \sum\limits_{j=0}^n a \, x^j = a - a \, x^{n+1}

Отсюда выражаем сумму геометрической прогрессии

∑j=0na xj=a⋅1−xn+11−x\sum\limits_{j=0}^n a \, x^j = a \cdot \frac{1-x^{n+1}}{1-x}

Арифметическая прогрессия. Продолжаем идти против хронологии школьной математики. Теперь давайте найдём сумму арифметической прогрессии

∑j=0n(a+b j)=∑0   ⁣⩽   ⁣j⩽n(a+b j)=∑0   ⁣⩽   ⁣n−j⩽n(a+b (n−j))==∑0   ⁣⩽   ⁣j⩽n(a+b n−b j)=∑0   ⁣⩽   ⁣j⩽n(2a+b n)−∑0   ⁣⩽   ⁣j⩽n(a+b j)==(n+1) (2a+b n)−∑j=0n(a+b j)\align{ \sum\limits_{j=0}^n (a + b \, j) &= \sum\limits_{0 \;\! \le \;\! j \le n} (a + b \, j) = \sum\limits_{0 \;\! \le \;\! n-j \le n} \bigl( a + b \, (n-j) \bigr) = \\ &= \sum\limits_{0 \;\! \le \;\! j \le n} (a + b \, n - b \, j ) = \sum\limits_{0 \;\! \le \;\! j \le n} (2a + b \, n) - \sum\limits_{0 \;\! \le \;\! j \le n} (a + b \, j ) = \\ &= (n+1) \, (2a + b \, n) - \sum\limits_{j=0}^n (a + b \, j) }

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

∑j=0n(a+b j)=a (n+1)+b n (n+1)/2\sum\limits_{j=0}^n (a + b \, j) = a \, (n+1) + b \, n \, (n+1) / 2
1

Упростите сумму, используя замену индекса или другие свойства

∑1   ⁣⩽   ⁣i<j⩽n(xi−xj)\sum\limits_{1 \;\! \le \;\! i < j \le n} (x_i - x_j)
2

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

∑j=1nj2=n (n+1) (2n+1)6\sum\limits_{j=1}^n j^2 = \frac{n \, (n+1) \, (2n+1)}{6}
3

Не применяя метод математической индукции и не дифференцируя суммируемое выражение, докажите, что

∑j=0nj xj=n xn+2−(n+1) xn+1+x(x−1)2для x≠1\sum\limits_{j=0}^n j \, x^j = \frac{n \, x^{n+2} - (n+1) \, x^{n+1} + x}{(x-1)^2} \quad\text{для}~ x \neq 1

Скобка Айверсона

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

Скобка Айверсона

Скобка Айверсона — функция от условия

[условие]={1 if условие истинно0 if условие ложно[\text{условие}] = \cases{1 & \if \text{условие истинно} \\ 0 & \if \text{условие ложно}}

С помощью этого обозначения можно просто и лаконично определить символ Кронекера δij=[i=j]\delta_{ij} = [i = j], индикаторную функцию 1A(x)=[x∈A]\mathbf{1}_A(x) = [x \in A], функцию знака числа sign⁡(x)=[x>0]−[x<0]\sign(x) = [x > 0] - [x < 0].

Скобка Айверсона очень удобная именно для операций с суммами. Можно записать сумму с соотношением R(j)R(j) как сумму по всем jj

∑R(j)aj=∑jaj⋅[R(j)]\sum\limits_{R(j)} a_j = \sum\limits_j a_j \cdot \bigl[ R(j) \bigr]

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

∑R(p(j))ap(j)=∑jap(j)⋅[R(p(j))]=∑i∑jai⋅[R(i)]⋅[i=p(j)]=∑iai⋅[R(i)]⋅∑i[i=p(j)]\sum\limits_{R(p(j))} a_{p(j)} = \sum\limits_j a_{p(j)} \cdot \bigl[ R\bigl(p(j)\bigr) \bigr] = \sum\limits_i \sum\limits_j a_i \cdot \bigl[ R(i) \bigr] \cdot \bigl[ i = p(j) \bigr] = \sum\limits_i a_i \cdot \bigl[ R(i) \bigr] \cdot \sum\limits_i \bigl[ i = p(j) \bigr]

Если функция pp задаёт перестановку чисел на области суммирования, то [i=p(j)]\bigl[ i = p(j) \bigr] будет равно 11 лишь единожды, а значит ∑i[i=p(j)]=1\sum\limits_i \bigl[ i = p(j) \bigr] = 1. В итоге получаем то, что требовалось доказать

∑R(p(j)ap(j)=∑R(i)ai\sum\limits_{R(p(j)} a_{p(j)} = \sum\limits_{R(i)} a_i

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

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

∑0   ⁣⩽   ⁣i⩽n ∑0   ⁣⩽   ⁣j⩽nai,j=∑0   ⁣⩽   ⁣i,j⩽nai,j∑0   ⁣⩽   ⁣iln ∑0   ⁣⩽   ⁣j⩽iai,j=∑0   ⁣⩽   ⁣i⩽j⩽nai,j\sum\limits_{0 \;\! \le \;\! i \le n} ~ \sum\limits_{0 \;\! \le \;\! j \le n} a_{i, \- j} = \sum\limits_{0 \;\! \le \;\! i, j \le n} a_{i, \- j} \qquad \sum\limits_{0 \;\! \le \;\! i \l n} ~ \sum\limits_{0 \;\! \le \;\! j \le i} a_{i, \- j} = \sum\limits_{0 \;\! \le \;\! i \le j \le n} a_{i, \- j}

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

Комбинированные индексы. Рассмотрим сумму с комбинированными индексами суммирования

∑1   ⁣⩽   ⁣i<j⩽n(ai+aj)\sum\limits_{1 \;\! \le \;\! i < j \le n} (a_i + a_j)

Каждый элемент aka_k появляется в сумме n−kn-k раз как aia_i для j>kj > k и k−1k-1 раз как aja_j для i<ki < k. То есть всего каждый элемент aka_k появляется в сумме (n−k)+(k−1)=n−1(n-k)+(k-1) = n-1 раз. Тогда

∑1   ⁣⩽   ⁣i<j⩽n(ai+aj)=∑k=1n(n−1) ak=(n−1)⋅∑k=1nak\sum\limits_{1 \;\! \le \;\! i < j \le n} (a_i + a_j) = \sum\limits_{k=1}^n (n-1) \, a_k = (n-1) \cdot \sum\limits_{k=1}^n a_k

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

∑i=1n∑j=1iai,j=∑i,jai,j⋅[1⩽i⩽n]⋅[1⩽j⩽i]==∑i,jai,j⋅[1   ⁣⩽   ⁣j⩽n]⋅[j⩽i⩽n]=∑j=1n∑i=jnai,j\align{ \sum\limits_{i=1}^n \sum\limits_{j=1}^i a_{i, \- j} &= \sum\limits_{i, \- j} a_{i, \- j} \cdot [1 \le i \le n] \cdot [1 \le j \le i] =\\ &= \sum\limits_{i, \- j} a_{i, \- j} \cdot [1 \;\! \le \;\! j \le n] \cdot [j \le i \le n] = \sum\limits_{j=1}^n \sum\limits_{i=j}^n a_{i, \- j} }

Здесь мы воспользовались тем, что

[1⩽i⩽n]⋅[1⩽j⩽i]=[1⩽j⩽i⩽n]=[1⩽j⩽n]⋅[j⩽i⩽n][1 \le i \le n] \cdot [1 \le j \le i] = [1 \le j \le i \le n] = [1 \le j \le n] \cdot [j \le i \le n]

В общем виде для двух соотношений R(i)R(i) и S(i,j)S(i, j) цепочка равенств скобок Айверсона выглядит похоже:

[R(i)]⋅[S(i,j)]=[R(i) и S(i,j)]=[∃ i∈ZR(i) и S(i,j)]⋅[R(i) и S(i,j)]\bigl[ R(i) \bigr] \cdot \bigl[ S(i, j) \bigr] = \bigl[ R(i) ~\text{и}~ S(i, j) \bigr] = \bigl[ \exists\, i \in \ZZ \? R(i) ~\text{и}~ S(i, j) \bigr] \cdot \bigl[ R(i) ~\text{и}~ S(i, j) \bigr]