§ 6.2. Математическая индукция

Слово «индукция» используется в математике в очень специфическом техническом значении. Иногда к нему добавляют определение математическая, как в названии данного параграфа. Однако это слово имеет множество значений, 12 из которых приведены в «Оксфордском словаре английского языка». Математическое значение слова «индукция» происходит из традиционного его значения, употребляемого в логике, которое близко к повседневному употреблению. Ссылаясь на «Оксфордский словарь английского языка», «индукция» в таком смысле — это

«процесс выведения общего закона или принципа из наблюдаемых частных случаев.»

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

Часто цитируемый пример ошибки, к которой может привести индукция, — это утверждение Ферма, высказанное Френиклю, о том, что все числа вида

будут простыми. Он, вероятно, проверил гипотезу для , что довольно просто, а затем сделал обобщение. Следующее число

довольно велико, если все, что у вас есть — это ручка и бумага. Был ли Ферма напуган размерами числа, или допустил ошибку при его вычислении? Вероятно, мы этого никогда не узнаем. Но, как мы видели, на самом деле составное число, и Эйлер был первым, кто в 1738 году нашел его делитель (мы будем подробно изучать эти числа в главе 10). С тех пор ошибка Ферма стала предупреждением об опасности обобщений на основе нескольких примеров.

В XVII столетии ряд математиков, и Ферма среди них, начали проявлять беспокойство по поводу отсутствия доверия к результатам, доказанным по индукции. Это побудило их развить метод, который очень подходит для доказательства фактов, продиктованных обобщением численных экспериментов, т.е. результатов, полученных ординарной индукцией. Новый метод получил известность как математическая индукция, или конечная индукция, или рекуррентное рассуждение. В трактате Б. Паскаля «Об арифметическом треугольнике», опубликованном в 1654 году, мы найдем объяснение метода математической индукции практически в современном виде. Конечно, «арифметический треугольник» из названия трактата сейчас известен как треугольник Паскаля. Паскаль, человек многих талантов, был первоклассным геометром и физиком. Именно он изобрел первую механическую машину для вычислений (калькулятор). Его «Мысли» — классика французской литературы.

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

что минимальное число ходов, требуемое для передвижения башни из дисков в головоломке «Ханойские башни», равно Отметим, что в действительности мы имеем бесконечно много утверждений, пронумерованных натуральными числами. А наш эксперимент говорит нам только, что эти утверждения справедливы для и не более.

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

Принцип математической индукции. Предположим, что для каждого натурального числа есть утверждение обладающее следующими двумя свойствами:

(1) верно;

(2) если верно для натурального к, то также верно.

Тогда справедливо для всех натуральных

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

Конечно, это рассуждение не доказывает принципа математической индукции. На самом деле, в некотором смысле, он вообще не может быть доказан! Анри Пуанкаре (Poincare), один из известных математиков XIX столетия, очень хорошо объясняет этот момент:

«Суждение, на котором основан способ рекуррентного рассуждения, может быть изложено в других формах; можно сказать, например, что в бесконечно большом множестве различных натуральных чисел всегда есть одно, которое меньше других. Можно легко переходить от одного выражения к другому и таким образом создавать иллюзию доказательства законности рассуждения путем рекурренции. Но в конце концов всегда придется остановиться; мы всегда придем к недоказуемой аксиоме, которая, в сущности, будет не что иное, как предположение, подлежащее доказательству, но только переведенное на другой язык.»

Так почему мы все же верим в строгость принципа индукции? Снова обратимся к Пуанкаре за помощью:

«Здесь сказывается только утверждение могущества разума, который способен постичь бесконечное повторение одного и того же акта, раз этот акт оказался возможным однажды.»

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

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

короче: мы хотим доказать, что Согласно принципу математической индукции, это будет верно для любого натурального если мы сможем доказать две вещи. Сначала мы должны проверить формулу для головоломки с 1 диском. Но мы уже убедились, что Так что первый шаг уже сделан. На математическом жаргоне он называется базой индукции.

Далее нужно сделать индуктивный переход, или шаг индукции, т.е. показать, что если утверждение верно для какого-то то оно верно и для Индуктивный переход основывается на двух моментах:

• Предположение о том, что утверждение верно для некоторого к 1. В нашем примере это означает гипотетическое равенство для некоторого к 1. Такое предположение называется предположением индукции.

• Какая-нибудь связь между . В примере — это рекуррентное соотношение:

Итак, предположим, что для некоторого к 1. Из рекуррентной формулы следует, что

Таким образом, условие (2) принципа математической индукции в нашем случае тоже верно. Теперь принцип математической индукции дает: так как (1) и (2) справедливы, то для всех натуральных

Зная минимальное число ходов, приводящих к решению задачи «Ханойские башни», мы можем теперь подсчитать оставшееся время до конца света. Напомним, что башня в индийском храме состоит из 64 дисков. Поэтому общее число перемещений, которые жрецу надо сделать со дня творения, равно Мало этого, нам еще хочется знать, сколько времени займет этот процесс. Предположим, что жрецу для

перестановки одного диска потребуется, в среднем, 30 минут. Диски, разумеется, имеют разные размеры. Нам не сказано насколько велик максимальный из них, но, по-видимому, не маленький, поскольку создал его сам Господь. А так как они, к тому же, сделаны из золота, то должны быть довольно тяжелыми. Поэтому полчаса — достаточно осторожное предположение. Величина 264 имеет порядок 1019, и несложные вычисления показывают, что жрецу потребуется около 1014 лет, чтобы перенести все диски. Таким образом, считая, что от Большого Взрыва прошло около 1011 лет, можно прикинуть, сколько еще осталось.

Эта легенда впервые была опубликована в Париже в 1883 году, одновременно с головоломкой, неким Н. Клаусом из колледжа в Ли-Соу-Стэйна. Имя человека и название колледжа — в действительности, анаграммы имени Люка д'Амьен, преподавателя лицея Святого Людовика. Это математик Ф. Е. А. Люка (F. Е. A. Lucas), придумавший как головоломку, так и рассказ о ее происхождении. Его книга «Математические развлечения» 1894 года стала классикой предмета. Люка занимался и теорией чисел. В 10 и 11 главах мы разберем два теста неприводимости, которые он открыл. Используя один из них, Люка, не прибегая к помощи компьютеров (которых тогда еще и не было), показал, что число Мерсенна

является простым.