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

Пример 20. Важное свойство выпуклого многоугольника. Для того частного случая, когда геометрическая фигура является многоугольником, можно предложить и другое определение выпуклости. Именно можно назвать многоугольник выпуклым, если он обладает свойством (β): какую ни взять сторону многоугольника, многоугольник целиком лежит по одну сторону от неё, т. е. от прямой, служащей её продолжением.

Эти определения равносильны: (1) из (α) вытекает (β); (2) из (β) вытекает (α). Утверждения (1) и (2) легко доказываются от противного. Доказательство для (1) сейчас изложим; доказать (2) предоставляем читателю.

Итак, предположим, что в многоугольнике, обладающем свойством (α), нашлись две такие его точки P и Q, которые лежат по разные стороны от некоторой его стороны AB. Поскольку все точки отрезка AB принадлежат многоугольнику, ему будут принадлежать и все точки треугольников PAB и QAB. Таким образом, отрезок AB является общей стороной треугольников PAB и QAB, расположенных хотя и по разные стороны от этого отрезка, но целиком в пределах рассматриваемого многоугольника. Очевидно, что такого не может быть, коль скоро AB является одной из сторон этого многоугольника.

§ 7. Индукция

Доказательства методом математической индукции

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

Пример 21. Доказать, что всегда 1 + 2 + 3 + … + n = n (n + 1)/2. Рассуждаем так. Во-первых, для n = 1 это утверждение верно; действительно:

Во-вторых, предположив, что наше утверждение верно для n = k, убеждаемся, что тогда оно верно и для n = k + 1; действительно:

Значит, наше утверждение верно для всех значений n. Действительно, оно верно для n = 1 (это было наше «во-первых»), а тогда в силу «во-вторых» оно верно для n = 2, откуда в силу того же «во-вторых» оно оказывается верным и для n = 3 и т. д.

Пример 22. Доказать, что справедливо равенство Ададурова (названное по имени Василия Евдокимовича Ададурова, российского математика XVIII в., который это равенство нашёл[140])

1³ + 2³ + 3³ + … + n³ = (1 + 2 + 3 + … + n)².

Доказываем по индукции. Для n = 1 проверяем непосредственно. Предположим, что равенство верно при n = k. Докажем, что тогда оно верно и при n = k + 1 (при этом используем результат примера 21):

Приведённое выше рассуждение показывает, что наше равенство верно не только при n = 1, но и при n = 2, n = 3 и т. д., т. е. при всех n.

Пример 23. Доказать, что при всех n справедливо равенство

Вы легко убедитесь в этом, воспользовавшись описанным методом.

Изложенный метод рассуждения требует установления двух фактов: (1) интересующее нас утверждение верно для единицы; (2) если интересующее нас утверждение верно для какого-то числа k, то оно верно и для следующего за ним числа k + 1. Если оба факта установлены, тогда, переходя от 1 к 2, от 2 к 3 и т. д., убеждаемся, как в только что приведённом примере, что рассматриваемое утверждение верно для всех натуральных чисел.

Первый факт называется базисом индукции, второй – индукционным переходом, или шагом индукции. Индукционный переход включает в себя посылку, или предположение индукции, или индукционное предположение и заключение. Смысл посылки: рассматриваемое утверждение верно при n = k. Смысл заключения: рассматриваемое утверждение верно при n = k + 1. Сам же индукционный переход состоит в переходе от посылки к заключению, т. е. в заявлении, что заключение верно, коль скоро верна посылка. Весь в целом логический приём, позволяющий заключить, что рассматриваемое утверждение верно для всех натуральных чисел, коль скоро справедливы и базис, и переход, называется так: принцип математической индукции. Использование этого принципа и составляет метод математической индукции.

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

Сам параметр называется параметром индукции; говорят также, что происходит индукция по данному параметру.

Утверждение A при значении параметра, равном 1, принято обозначать через A(1), при значении параметра, равном 2, – через A(2) и т. д. В примере 21 A(10) есть

Утверждения A(1), A(2), A(3), … называют частными формулировками, а утверждение «Для всякого n имеет место A(n)» – универсальной формулировкой. Таким образом, в наших теперешних обозначениях базис индукции есть не что иное, как частная формулировка A(1). А шаг индукции, или индукционный переход, есть утверждение «Каково бы ни было n, из истинности частной формулировки A(n) вытекает истинность частной формулировки A(n + 1)».

Доказательство по методу индукции начинается с того, что формулируются два утверждения – базис индукции и её шаг. Здесь проблем нет. Проблема состоит в том, чтобы доказать оба эти утверждения. Если это не удаётся, наши надежды на применение метода математической индукции не оправдываются. Зато если нам повезло, если удалось доказать и базис, и шаг, то доказательство универсальной формулировки мы получаем уже без всякого труда, применяя следующее стандартное рассуждение:

Утверждение A(1) истинно, поскольку оно есть базис индукции. Применяя к нему индукционный переход, получаем, что истинно и утверждение A(2). Применяя к A(2) индукционный переход, получаем, что истинно и утверждение A(3). Применяя к A(3) индукционный переход, получаем, что истинно и утверждение A(4). Таким образом мы можем дойти до каждого значения n и убедиться, что A(n) истинно. Следовательно, для всякого n имеет место A(n), а это и есть та универсальная формулировка, которую требовалось доказать.

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