Математика · объяснение и практика

Математическая индукция: зачем нужны база и переход

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

Синяя и оранжевая половины складываются в целый круг.

В теме Доказательства и комбинаторные модели · Учебная карта

Главная мысль

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

Две независимые обязанности

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

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

Пример с нечётными слагаемыми

Докажем, что сумма первых n положительных нечётных чисел равна n². При n=1 обе стороны равны единице. Предположим равенство для некоторого k. Следующее нечётное число равно 2k+1, поэтому новая сумма равна k²+2k+1=(k+1)². Это именно нужная формула с заменой номера на следующий.

В переходе нельзя добавлять 2k−1: этот член уже учтён в первых k слагаемых. Полезно назвать, что именно изменилось при увеличении номера. Здесь появился один новый член, а справа квадрат нового номера. Алгебраическое тождество связывает две записи и завершает общий шаг, не обращаясь к проверке каждого следующего числа отдельно.

Пример

Докажите делимость 7ⁿ−1 на шесть для всех целых n≥1.

База: 7−1=6. Для перехода 7^(k+1)−1=7(7^k−1)+6. По предположению первое выражение в скобках кратно шести, поэтому оба слагаемых справа кратны шести. Следовательно, нужная делимость переносится на k+1.

Почему отсутствие базы ломает доказательство

Условие «из утверждения на k следует утверждение на k+1» может быть верным даже тогда, когда ни один случай не истинен. Например, из неравенства k>k+1 следует ложное неравенство следующего вида как условная связь с невозможной гипотезой; запускающей базы нет. Поэтому один только переход не даёт фактической истинности ни одного номера.

Если переход перескакивает через номер, например от k к k+2, одной базы может не хватить: запускается лишь одна чётность. Тогда нужны соответствующие начальные случаи или другой переход. Сильная индукция разрешает использовать все предыдущие случаи до k, но также требует явной базы и правильно заявленной области. Выбор формы определяется задачей, а не желанием пропустить трудный начальный шаг.

От чтения к действию

А теперь — вы

Требуется доказать P(n) для всех целых n≥3. Уже доказан переход P(k)⇒P(k+1) при любом k≥3. Что ещё необходимо для обычной индукции?

Частые вопросы

Почему индукционное предположение не является круговым доказательством?

Доказывается условное следствие для произвольного шага. Истинность начального случая установлена отдельно; после этого условная связь переносит её дальше.

Если переход идёт на два вперёд, достаточно базы n=1?

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

Источники и работа с материалом

Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.

Продолжить разбираться