Апология математики (сборник статей)

Изложенный метод рассуждения требует установления двух фактов: (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). Поэтому принцип математической индукции позволяет делать заключение об истинности универсальной формулировки, как только установлены истинность базиса индукции и индукционного перехода.

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