Принцип математической индукции

Попробуйте ответить на вопрос: упадет ли самая последняя доминошка, независимо от количества доминошек, если все доминошки выставлены в ряд и :

• первая доминошка точно упадет
• при падении любой доминошки под номером n, точно упадет следующаяя (т.е. под номером n + 1)

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

Итак, что такое математическая индукция?

Для начала вспомним что такое утверждение в математике - это такое выражение, которое является или истинным, или ложным. В программировании, можно сказать, что выражение - это все что угодно, что возвращает тип boolean (true или false).

Пусть у нас есть последовательность утверждений: А(1), А(2), А(3), ... А(n). Если мы можем утверждение A(n) доказать на основании предыдущих утверждений, то говорят что мы можем доказать утверждение A(n) по индукции. Это напоминает динамическое программирование в том плане, что мы для нахождения значения выражения для n мы должны рассмотреть более простые выражения, с меньшим значением n.

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

Чтобы провести доказательство некоторого утверждения A(n) для любого натурального n по индукции, нужно

1. Доказать, что утверждение верно при n=1 (это можно сделать просто подстановкой)
2. Приняв верность утверждения A(n), вывести что это же утверждение будет верно для A(n+1).

Примеры

Обычно индукцию рассматривают на конкретных примерах.

Сумма первых положительных натуральных чисел

В одном учебнике вы нашли формулу суммы первых n натуральных чисел, т.е. чему равна сумма 1 + 2 + 3 + ... + n

Да, мы можем вывести эту формулу (расположив числа в ряд, под которым расположен такой же ряд, но наоборот. Сумма таких 2-х чисел (n + 1), таких чисел n, но сумму мы учитывали 2 раза, поэтому делим на 2).

Но представим, что мы просто нашли формулу и не знаем, правдива ли она. Мы можем подставить в формулу вместо n любое число: 2, 7, 1001, 578561 и вручную посчитать сумму, а после сравнить эти числа. Но как доказать, что эта формула верна для любого n, при условии что n - бесконечно много?

Применяя метод математической индукции, нужно доказать, что

• для n = 1 формула верна (база)
• если для любого n формула верна, то она верна и для (n + 1) (индукционны переход)

Доказав второй пункт, мы докажем что если для n = 1 (а это мы можем доказать, просто подставив вместо n единицу), то формула верна и для (n+1), т.е. для 2. Если формула верна для 2, то она равна и для 3 и т.д.

Подставим n = 1 в формулу выше, и получим что 1 = 1 что, разумеется, верно.

Предположим, что наша формула верна для любого n, т.е.

Теперь мы хотим проверить, что будет если мы заменим n на (n+1). Слева мы должны добавить к исходному выражению n+1 (зеленым цветом), т.к. именно эту сумму мы теперь находим. Справа мы должны заменить n на (n+1) (синим цветом).

Заметим, что сумму первых чисел, от 1 до n мы уже можем заменить формулой 1. Справа сложим единицы (все изменения здесь и далее выделены зеленым цветом)

Посмотрим на выражение слева. Внесем второе выражение (n+1) под дробь, затем вынесем (n+1) и получим тоже самое выражение, что стояло у нас в правой части.

Значит второй пункт доказан и формула 1 верна для любого натурального n.

Сумма кубов и квадрат суммы

Доказать следующее равенство

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

Для 3 равенство верно, но всегда ли будет так? Попробуем доказать это по индукции.

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

Заменяем в формуле n на n+1, для этого и слева, и справа прибавляем (n+1)

Заменим в левой части сумму от 1 до n по формуле 2

Теперь посмотрим на правую часть. Вспомним формулу квадрат суммы

Теперь преобразуем выражение справа как сумму (1+2+3+...+n) и (n+1). Мы получим следующее (разными цветами выделены выражения, которые мы принимаем в качестве a и b)

В прошлой задаче мы уже выяснили формулу суммы первых n натуральных положительных чисел (формула 1). Подставим эту формулу в выражение

Дальше мы можем сократь на 2, вынести (n+1)^2 за скобку и увидим, что мы получили точно такое же выражение, как было в левой части формулы 2 после прибавления (n+1). Значит формула 2 верна для любого натурального n.

Выбраться из пустыни

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

В пустыне стоит родник с чистой питьевой водой (воды так много, что можно считать что ее неограниченное количество). У родника находится путешественник, который выпивает 1 литр воды каждые 5 км (без воды он не проживет). У путешественника есть рюкзак и 5 литровых бутылок, которые он может наполнить водой (т.е. путешественник может нести не более 5 литров воды с собой), но при этом он может оставлять в любой точке на карте любое количество бутылок с водой (будем считать что количество пустых бутылок тоже бесконечно много и они волшебным образом появляются при желании). Нужно доказать, что путешественник сможет пройти любое количество километров от родника.

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

Если путешественнику достаточно только 2 бутылок из 5, чтобы пройти 5 км и вернуться, то он может оставить оставшиеся 3 бутылки через 5 км.

Повторяя такой маршрут, он сможет накопить на расстоянии 5км любое количество бутылок, а значит любой запас воды в любом количестве. Значит, чтобы перейти следующие 5 км (n+1), мы должны сделать достаточный запас воды в предыдущем месте (n), а в предыдущем месте мы можем сделать запас в любом количестве. Значит и в следующем месте мы можем сделать запас влюбом количестве.

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

Доказательство делимости на 6

Доказать, что при любом натуральном n выражение

делится на 6.

Для n = 1 выражние пример вид 2 + 3 + 7 = 12, 12 делится на 6.

Заменим n на (n+1), получим следующее выражение

Мы получили сумму двух выражений, и нам нужно доказать что их сумма делится на 6. Посмотрим на первую сумму - это исходное выражение, т.е. выражение для n, которое делится на 6. Второе выражение - произведение 6 и скобки (не так и важно значение в скобках), значит оно также делится на 6.

Сумма углов выпуклого многоугольника

Доказать, что сумма углов выпуклого многоугольника равна

Для самого простого случая, т.е. треугольника (где n = 3), формула верна (сумма углов треугольника равна 180 градусов)

Попробуем доказать, что формула верна при переходе от n к (n+1).

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

Черно белая плоскость

Пусть у нас имеется некоторая плоскость (возьмем для примера прямоугольный лист бумаги). Мы можем провести на этой плоскости прямые линии. Таким образом у нас образуются некоторые участки на плоскости в виде многоугольников.

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

Для начала докажем, что при 1 линии мы можем это сделать, т.к. любую плоскость прямая делит на 2 части. Одну часть мы красим в белый - другую - в черный.

Докажем что это можно сделать для (n+1) линии, считая что это можно сделать для n линий.

Предположим, что у условие верно для 2-х линий. Проведем третью линию (красную).

Заметим, что эта линия делит плоскость на 2 части - условно слева от линии и справа от линии. В каждой из этих двух отдельных плоскостей соседние участки не пересекаются. Но красная линии делит некоторые участки (те, что пересекает) на 2 участка поменьше, и они одного цвета. Если мы возьмем одну из двух плоскостей, и поменяем в ней цвета (с черного на белый и наоборот), то сосение участки все равно не будут пересекаться (если мы разделим плоскость только 1-й линией, то не важно какая из полученных 2-х плоскостей будет белой, а какая - черной). Значит, если мы возьмем любую из двух частей (слева или справа) и поменяем в ней цвета на обратные, то:

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

Таким образом, мы доказали что при переходе от n линий к n + 1 мы всегда сможем получить плоскость из участков, которые будут разного цвета. Для этого нужно просто поменять все цвета на противоположные с одной стороны от новой линии.

Заключение

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

Рассмотрим такую задачу - доказать, что все люди лысые. При n=1, мы получим, что человек с одним волосом на голове - лысый, что пожалуй верно (хотя зависит от строгости определения "лысый"). Если мы добавим лысому человеку 1 волос (т.е. перейдем от n к (n+1)), то человек останется лысым. Значит, какое бы мы значение n не выбрали, все люди будут лысыми - очевидно это не так.

Мы не уточнили, что означает "лысый", но если бы мы выбрали его как (n<100), где n-количество волос, сразу бы увидели ошибку, т.к. теперь задачу звучит: "любое натуральное число меньше 100". Здесь не нужно никакой индукции, чтобы понять что это не так.

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

Ошибка в данном случае в переходе. Из того, что утверждение верно для n=1 не следует, что оно верно для n=2. Но что, если мы сможем доказать, что любые 2 девушки имеют одинаковый цвет глаз?

Рассмоторим на общем примере - у нас есть 5 кружков (с буквами от А до Е), и мы хотим доказать что они все равны (например, цветом окружности).

Для n=2 утверждение верно (можно выбрать любые 2 окружности). Добавим еще одну окружность (например В). Если мы уберем любую окружность, то получим n=2, и у нас есть 3 варианта (можем убрать любую окружность), но любые 2 окружности равны. Значит, все окружности равны (вне зависимости от признака, по которому мы сравнивали).

При доказательстве по индукции нужно быть особенно осторожным, при переходе к индукционному переходу. Не всегда можно увидеть ошибку в выражении "из этого следует".