общем виде, и нет нужды повторять его каждый раз применительно к тому или иному конкретному выражению 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, что и требовалось.

Иногда утверждение может и не содержать параметра в явном виде и требуется сообразительность, чтобы его туда ввести (примеры 26 и 27).

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

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

Базис справедлив: ведь при n = 1 прямая ровно одна и достаточно просто раскрасить в разные цвета те две части, на которые она делит плоскость. Посылка индукционного шага состоит в предположении, что правильную раскраску можно всегда осуществить в случае k прямых. Заключение – в утверждении, что правильную раскраску всегда можно осуществить для k + 1 прямых. Переход от посылки к заключению, показанный на рис. 2, состоит в следующем. На карте, образованной k + 1 прямыми, выделим одну прямую – на рис. 2, а она показана жирной линией и помечена буквой p. Удалив эту прямую, получим карту, содержащую k прямых (рис. 2, б). Согласно индукционному предположению, полученная карта допускает правильную раскраску, которая показана на рис. 2, в. На раскрашенной карте восстанавливаем удалённую прямую (рис. 2, г), отчего правильность раскраски, разумеется, нарушается. Однако она сохранится в каждой из полуплоскостей, на которые выделенная прямая разбивает плоскость; нарушения будут иметь место лишь там, где граница между участками проходит по прямой p. Поэтому если в одной из названных полуплоскостей раскраску не менять, а в другой заменить каждый из двух цветов на противоположный, то вся карта с k + 1 прямой окажется правильно раскрашенной (рис. 2, д).

Пример 27. Выпуклый многоугольник целиком покрыт другим выпуклым многоугольником. (Например, на рис. 3 многоугольник ABCDEFG целиком покрыт многоугольником IJKLMNO.) Доказать, что периметр внутреннего многоугольника не превосходит периметра многоугольника внешнего.

Будем доказывать данное утверждение методом математической индукции. Чтобы применить этот метод, надлежит ввести параметр. Сообразительности здесь потребуется несколько больше, чем в примере 26. Назовём свободной всякую сторону внутреннего многоугольника, которая не лежит ни на какой стороне внешнего многоугольника. (Так, на рис. 3 свободными являются стороны AB, BC, CD, EF, GA, но не стороны DE и FG.) В качестве параметра индукции возьмём количество свободных сторон, точнее говоря, количество свободных сторон плюс единица (поскольку свободных сторон может и не быть, а мы условились начинать натуральный ряд не с ноля, а с единицы). Сформулируем теперь более развёрнуто утверждение, которое собираемся доказывать индукцией по этому параметру: каково бы ни было натуральное число n, для всяких двух вложенных друг в друга выпуклых многоугольников, у которых число свободных сторон равно n – 1 или меньше, периметр внутреннего многоугольника не превосходит периметра внешнего многоугольника.

В базисе индукции значение параметра равно единице, а это значит, что свободных сторон нет вовсе. Тогда утверждение очевидно: ведь в этом случае каждая сторона внутреннего многоугольника является частью какой-либо стороны внешнего многоугольника. Предположим теперь, что утверждение верно для всех случаев, когда в паре вложенных многоугольников имеется k свободных сторон. Докажем его для всех случаев, когда в паре вложенных многоугольников имеется k + 1 свободных сторон. Итак, пусть R есть внутренний многоугольник, Т – внешний и количество свободных сторон есть k + 1. Нам нужно доказать, что p(R) ≤ p(T), где p(R) и р(Т) – периметры многоугольников R и T. Берём