Перейти к содержимому
Topos Uranos
Русский

Суммы, прогрессии и индукция

Краткое содержание

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

Цели обучения

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

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

В уроке об аксиомах Пеано появились суммы многих слагаемых, подчиняющиеся некоторому правилу, например 1+2+⋯+n1 + 2 + \cdots + n. Многоточие поручает читателю угадать это правило; знак суммирования его объявляет. Если am,am+1,…,ana_m, a_{m + 1}, \ldots, a_n являются числами, причём m≤nm \leq n, то пишут

∑k=mnak=am+am+1+⋯+an\sum_{k=m}^{n} a_k = a_m + a_{m + 1} + \cdots + a_n

и читают «сумма aka_k по kk от mm до nn». Буква kk является индексом суммирования; mm и nn являются её нижним и верхним пределами, а aka_k есть её общий член. Сумма содержит n−m+1n - m + 1 слагаемых. Индекс является немой переменной: значение суммы не зависит от того, какой буквой он обозначен, так что ∑k=1nk2\sum_{k=1}^{n} k^2 и ∑j=1nj2\sum_{j=1}^{n} j^2 представляют собой одно и то же число. Индекс пробегает натуральные числа; члены же могут быть числами другого рода. В этом уроке, помимо натуральных, встречаются целые числа вместе с отрицательными и дроби, которые строятся в следующем разделе: здесь они используются заранее, и из их свойств применяются только элементарные правила вычислений и порядка (коммутативность, ассоциативность, дистрибутивность, правила знаков, вычитание и деление на ненулевое число). Приведённые ниже свойства знака суммирования доказываются с помощью этих правил и, следовательно, верны для членов любого из этих родов.

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

∑k=mmak=am,∑k=mn+1ak=∑k=mnak+an+1\sum_{k=m}^{m} a_k = a_m, \qquad \sum_{k=m}^{n + 1} a_k = \sum_{k=m}^{n} a_k + a_{n + 1}

Это определение начинается с mm, тогда как теорема о рекурсии в той форме, в какой она была сформулирована, определяет функции начиная с 11. Однако достаточно перенести индекс: вместо суммы до nn определяется сумма qq первых членов начиная с ama_m. При начальном значении ama_m и правиле gq(x)=x+am+qg_q(x) = x + a_{m + q} теорема о рекурсии даёт единственную функцию FF из N\mathbb{N} в числа, такую что F(1)=amF(1) = a_m и F(q+1)=F(q)+am+qF(q + 1) = F(q) + a_{m + q} для всякого натурального qq. Тогда при n≥mn \geq m сумма до nn определяется как значение FF на числе её слагаемых, n−m+1n - m + 1, которое является натуральным, поскольку m<n+1m < n + 1:

∑k=mnak=F(n−m+1)\sum_{k=m}^{n} a_k = F(n - m + 1)

При n=mn = m получаем F(1)=amF(1) = a_m, а при q=n−m+1q = n - m + 1, поскольку m+q=n+1m + q = n + 1, равенство F(q+1)=F(q)+am+qF(q + 1) = F(q) + a_{m + q} есть в точности второе правило определения. Следовательно, определение по рекурсии, начинающееся с mm, задаёт единственную сумму для каждого n≥mn \geq m, а при m=1m = 1 оно совпадает с тем, которое непосредственно даёт теорема о рекурсии, поскольку тогда F(n)=∑k=1nakF(n) = \sum_{k=1}^{n} a_k.

В этих обозначениях формула, доказанная по индукции в уроке об аксиомах Пеано, формула суммы nn первых натуральных чисел, записывается так:

∑k=1nk=n(n+1)2\sum_{k=1}^{n} k = \frac{n(n + 1)}{2}

Сумма квадратов, ∑k=1nk2\sum_{k=1}^{n} k^2, является следующим шагом, и этот урок не ограничится тем, чтобы её проверить: параграф о телескопических суммах выводит её, не зная её заранее.

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

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

Пусть дано натуральное число n0n_0. Если свойство выполняется для n0n_0 и из того, что оно выполняется для произвольного натурального k≥n0k \geq n_0, следует, что оно выполняется и для k+1k + 1, то это свойство выполняется для всех натуральных n≥n0n \geq n_0. Идея состоит в том, чтобы перенумеровать натуральные числа начиная с n0n_0 и вернуться к обычному принципу индукции. Используются лемма из урока об операциях с натуральными числами, согласно которой всякое натуральное число, отличное от 11, является последователем, и монотонность сложения. На рисунке n0=4n_0 = 4 и p=3p = 3: под каждым натуральным числом начиная с n0n_0 стоит его новый номер qq.

Доказательство

  1. n0=p+1,Q(q)↔P(p+q)n_0 = p + 1, \quad Q(q) \leftrightarrow P(p + q)

    Если n0=1n_0 = 1, это принцип индукции. Иначе n0=p+1n_0 = p + 1 для некоторого натурального pp, и мы рассматриваем свойство QQ, утверждающее PP для p+qp + q.

  2. Q(1)↔P(p+1)↔P(n0)Q(1) \leftrightarrow P(\resaltar{p + 1}) \leftrightarrow P(\resaltar{n_0})

    Свойство QQ выполняется для 11, поскольку Q(1)Q(1) есть P(n0)P(n_0).

  3. P(p+q)→P((p+q)+1)=P(p+(q+1))P(p + q) \rightarrow P(\resaltar{(p + q) + 1}) = P(\resaltar{p + (q + 1)})

    Если Q(q)Q(q) выполняется, то, поскольку 1≤q1 \leq q, по монотонности сложения имеем p+q≥p+1=n0p + q \geq p + 1 = n_0, и данный шаг применим к k=p+qk = p + q: выполняется Q(q+1)Q(q + 1).

  4. n≥n0→(∃q∈N)(n=p+q)n \geq n_0 \rightarrow (\exists q \in \mathbb{N})(n = p + q)

    По принципу индукции Q(q)Q(q) верно для всякого qq. Всякое n≥n0n \geq n_0 имеет вид p+qp + q: если n=n0n = n_0, то при q=1q = 1, а если n=n0+ln = n_0 + l, то при q=1+lq = 1 + l.

Свойства знака суммирования

Из определения по рекурсии индукцией по верхнему пределу выводятся следующие свойства, справедливые для любых членов aka_k и bkb_k и для любого числа cc:

  1. Линейность: ∑k=mn(ak+bk)=∑k=mnak+∑k=mnbk\sum_{k=m}^{n} (a_k + b_k) = \sum_{k=m}^{n} a_k + \sum_{k=m}^{n} b_k и ∑k=mnc ak=c∑k=mnak\sum_{k=m}^{n} c\,a_k = c \sum_{k=m}^{n} a_k. В частности, сложить nn раз одну и ту же постоянную значит умножить её на nn: ∑k=1nc=nc\sum_{k=1}^{n} c = nc.
  2. Разложение: если m≤p<nm \leq p < n, то ∑k=mnak=∑k=mpak+∑k=p+1nak\sum_{k=m}^{n} a_k = \sum_{k=m}^{p} a_k + \sum_{k=p+1}^{n} a_k.
  3. Сдвиг индекса: для всякого натурального pp имеем ∑k=mnak=∑j=m+pn+paj−p\sum_{k=m}^{n} a_k = \sum_{j=m+p}^{n+p} a_{j - p}.
  4. Обращение порядка: ∑k=1nak=∑j=1nan+1−j\sum_{k=1}^{n} a_k = \sum_{j=1}^{n} a_{n + 1 - j}.
ТеоремаСвойства знака суммирования

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

Доказательство

  1. ∑k=mn+1(ak+bk)=∑k=mnak+∑k=mnbk+(an+1+bn+1)=∑k=mn+1ak+∑k=mn+1bk\sum_{k=m}^{n + 1} (a_k + b_k) = \resaltar{\sum_{k=m}^{n} a_k + \sum_{k=m}^{n} b_k} + (a_{n + 1} + b_{n + 1}) = \sum_{k=m}^{n + 1} a_k + \sum_{k=m}^{n + 1} b_k

    Линейность. При n=mn = m обе части равны am+bma_m + b_m. Если она верна для nn, применяются определение по рекурсии, предположение индукции, ассоциативность и коммутативность сложения. Точно так же с помощью дистрибутивности доказывается, что ∑k=mnc ak=c∑k=mnak\sum_{k=m}^{n} c\,a_k = c \sum_{k=m}^{n} a_k, и что ∑k=1nc=nc\sum_{k=1}^{n} c = nc, поскольку nc+c=(n+1)cnc + c = (n + 1)c.

  2. ∑k=mp+1ak=∑k=mpak+ap+1=∑k=mpak+∑k=p+1p+1ak\sum_{k=m}^{p + 1} a_k = \sum_{k=m}^{p} a_k + \resaltar{a_{p + 1}} = \sum_{k=m}^{p} a_k + \resaltar{\sum_{k=p+1}^{p + 1} a_k}

    Разложение при фиксированном pp, индукцией по nn начиная с p+1p + 1. При n=p+1n = p + 1 это определение по рекурсии, поскольку сумма из одного слагаемого есть само это слагаемое.

  3. ∑k=mn+1ak=∑k=mpak+∑k=p+1nak+an+1=∑k=mpak+∑k=p+1n+1ak\sum_{k=m}^{n + 1} a_k = \resaltar{\sum_{k=m}^{p} a_k + \sum_{k=p+1}^{n} a_k} + a_{n + 1} = \dato{d}{\sum_{k=m}^{p} a_k + \sum_{k=p+1}^{n + 1} a_k}

    Если разложение верно для nn, к обеим частям прибавляется член an+1a_{n + 1} и к каждой сумме применяется определение по рекурсии.

  4. ∑j=m+pn+1+paj−p=∑j=m+pn+paj−p+an+1=∑k=mnak+an+1=∑k=mn+1ak\sum_{j=m+p}^{n+1+p} a_{j - p} = \resaltar{\sum_{j=m+p}^{n+p} a_{j - p}} + a_{n + 1} = \resaltar{\sum_{k=m}^{n} a_k} + a_{n + 1} = \dato{s}{\sum_{k=m}^{n + 1} a_k}

    Сдвиг. При n=mn = m обе части равны ama_m. Если он верен для nn, то, поскольку верхний предел (n+p)+1(n + p) + 1 есть (n+1)+p(n + 1) + p, применяются определение по рекурсии и предположение индукции.

  5. ∑j=1n+1an+2−j=an+1+∑j=2n+1an+2−j=an+1+∑i=1nan+1−i\sum_{j=1}^{n + 1} a_{n + 2 - j} = a_{n + 1} + \resaltar{\sum_{j=2}^{n + 1} a_{n + 2 - j}} = a_{n + 1} + \resaltar{\sum_{i=1}^{n} a_{n + 1 - i}}

    Обращение, индукцией по nn. При n=1n = 1 обе части равны a1a_1. Если оно верно для nn, то по свойству разложения от обращённой суммы из n+1n + 1 членов отделяется первый член, и индекс сдвигается на единицу, при j=i+1j = i + 1.

  6. an+1+∑i=1nan+1−i=an+1+∑k=1nak=∑k=1n+1aka_{n + 1} + \resaltar{\sum_{i=1}^{n} a_{n + 1 - i}} = a_{n + 1} + \resaltar{\sum_{k=1}^{n} a_k} = \sum_{k=1}^{n + 1} a_k

    По предположению индукции последняя сумма равна ∑k=1nak\sum_{k=1}^{n} a_k; по коммутативности и определению по рекурсии получаем обращение для n+1n + 1.

Линейность позволяет свести сложную сумму к известным. Два последних свойства являются заменами переменной: сдвиг подставляет k=j−pk = j - p и пробегает те же члены с другой нумерацией, а обращение подставляет k=n+1−jk = n + 1 - j и пробегает их от последнего к первому. Однако с умножением сумма ведёт себя иначе: сумма произведений не равна произведению сумм. Достаточно примера с двумя слагаемыми и ak=bk=ka_k = b_k = k:

∑k=12k⋅k=1+4=5≠9=(1+2)(1+2)\sum_{k=1}^{2} k \cdot k = 1 + 4 = 5 \neq 9 = (1 + 2)(1 + 2)
УтверждениеСумма первых нечётных чисел

Доказать, что сумма nn первых нечётных чисел равна n2n^2. Линейность сводит эту сумму к двум уже известным, без новой индукции.

Доказательство

  1. 1+3+5+⋯+(2n−1)=∑k=1n(2k−1)1 + 3 + 5 + \cdots + (2n - 1) = \dato{s}{\sum_{k=1}^{n} (2k - 1)}

    Нечётное число, стоящее на месте kk, равно 2k−12k - 1: первое равно 11, второе равно 33, а стоящее на месте nn равно 2n−12n - 1. Искомая сумма записывается так.

  2. ∑k=1n(2k−1)=2∑k=1nk−∑k=1n1\sum_{k=1}^{n} \resaltar{(2k - 1)} = \resaltar{2 \sum_{k=1}^{n} k - \sum_{k=1}^{n} 1}

    По линейности сумма разлагается на две: удвоенная сумма чисел kk минус сумма nn единиц.

  3. 2∑k=1nk−∑k=1n1=n(n+1)−n2 \resaltar{\sum_{k=1}^{n} k} - \resaltar{\sum_{k=1}^{n} 1} = \resaltar{n(n + 1)} - \resaltar{n}

    Первая сумма есть сумма nn первых натуральных чисел, n(n+1)2\frac{n(n + 1)}{2}, и множитель 22 сокращает её знаменатель; вторая складывает nn раз число 11.

  4. n(n+1)−n=n2+n−n=n2\resaltar{n(n + 1)} - n = \resaltar{n^2 + n} - n = n^2

    Раскрываем скобки; члены nn и −n-n взаимно уничтожаются.

  5. k2−(k−1)2=2k−1k^2 - (k - 1)^2 = 2k - 1

    Рисунок показывает, почему это так: каждое нечётное число есть разность двух последовательных квадратов, уголок, превращающий квадрат со стороной k−1k - 1 в квадрат со стороной kk.