Пример 19. Иррациональность квадратного корня из двух. Геометрическое доказательство. Предположим, что этот корень рационален и выражается дробью Тогда Замечаем, что m² = 2n² ⇒ m² < 4n² ⇒ m < n + n и что n < n + m. Поэтому для тройки чисел (n, n, m) выполняются неравенства треугольника и возможен треугольник со сторонами длины n и m. По обратной теореме Пифагора этот треугольник прямоуголен, причём единичный отрезок укладывается в его катете n раз, а в гипотенузе – m раз. Следовательно, единичный отрезок служит общей мерой катета и гипотенузы этого равнобедренного прямоугольного треугольника, так что они соизмеримы, чего не может быть (см. пример 18).
Замечание. Выпуклые фигуры. Напомним, что геометрическая фигура называется выпуклой, если она обладает следующим свойством (α): для любых двух точек фигуры отрезок, соединяющий эти точки, находится в пределах этой фигуры. В качестве полезного упражнения рекомендуем читателю доказать, что для любой совокупности выпуклых фигур фигура, образованная их пересечением, непременно выпукла. В частности, если прямая пересекает выпуклый многоугольник, то она разбивает его на два выпуклых многоугольника. В самом деле, каждая из частей разбиения представляет собою пересечение исходного многоугольника с одной из тех двух полуплоскостей, на которые прямая разрезает плоскость, а всякая полуплоскость выпукла.
Пример 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])
Доказываем по индукции. Для 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), а это и есть та универсальная формулировка, которую требовалось доказать.
Принцип математической индукции заключается, по существу, в разрешении не проводить «стандартное рассуждение» в каждой отдельной ситуации. Действительно, стандартное рассуждение только что было обосновано в общем виде, и нет нужды повторять его каждый раз применительно к тому или иному конкретному выражению A(n). Поэтому принцип математической индукции позволяет делать заключение об истинности универсальной формулировки, как только установлены истинность базиса индукции и индукционного перехода.
Чтобы у читателя не создалось впечатления, что принцип индукции используется только для доказательства равенств, докажем с помощью этого принципа важное неравенство.
Пример 24. Доказать, что верно неравенство (1 + α)n ≥ 1 + nα, где α ≥ –1.
Базис индукции выполнен, поскольку при n = 1 левая и правая части одинаковы. Шаг индукции начинаем с предположения, что утверждение верно при n = k; таким образом, посылка шага индукции есть (1 + α)k ≥ 1 + kα. Умножая это неравенство на неотрицательное число 1 + α, получаем (1 + α)k+1 ≥ (1 + kα) (1 + α). Последнее неравенство переписываем так: (1 + α)k+1 ≥ 1 + (k +1)α + kα². Отбрасывая в правой части неотрицательный член kα², получаем: (1 + α)k+1 ≥ 1 + (k + 1)α. А это и есть заключение шага индукции. Итак, мы проверили и базис, и шаг. Доказательство методом индукции завершено.
Иногда приходится доказывать утверждение не для всех натуральных чисел, а для всех, начиная с некоторого числа; как поступать в таких случаях, показано в примере 25.
Пример 25. Доказать, что сумма углов выпуклого n-угольника равна 2(n – 2) d, где d – прямой угол.
Ясно, что утверждение, которое нужно доказать, имеет смысл лишь при n ≥ 3. Чтобы иметь право применить метод индукции, надо косметически изменить формулировку: сумма углов выпуклого (n + 2)-угольника равна 2nd. Такая формулировка уже имеет смысл при всех натуральных n. Базис составляет здесь известная теорема о сумме углов треугольника: сумма углов (1 + 2)-угольника равна 2 · 1d. Чтобы вывести заключение индукционного перехода [сумма углов многоугольника с числом сторон (k + 1) + 2 равна 2(k + 1) d] из его посылки (сумма углов многоугольника с числом сторон k + 2 равна 2kd), поступаем так. В многоугольнике с числом сторон (k + 1) + 2 берём две вершины, соседствующие с одной и той же вершиной, и соединяем их диагональю. Эта диагональ разобьёт наш многоугольник на две части – на треугольник и на (k + 2)-угольник. Сумма углов исходного многоугольника получается сложением суммы углов треугольника, каковая сумма есть 2d, и суммы углов (k + 2)-угольника, каковая сумма (посылка перехода!) есть 2kd; складывая, получаем: 2 (k + 1) d, что и требовалось.
