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

В теме Доказательства и комбинаторные модели · Учебная карта
Главная мысль
Математическая индукция требует доказать начальный случай и переход от произвольного допустимого 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, но также требует явной базы и правильно заявленной области. Выбор формы определяется задачей, а не желанием пропустить трудный начальный шаг.
От чтения к действию
А теперь — вы
Частые вопросы
Почему индукционное предположение не является круговым доказательством?
Доказывается условное следствие для произвольного шага. Истинность начального случая установлена отдельно; после этого условная связь переносит её дальше.
Если переход идёт на два вперёд, достаточно базы n=1?
Для всех положительных номеров обычно нет: такая цепь охватит лишь нечётные номера. Нужна также база другой чётности или дополнительная связь.
Источники и работа с материалом
Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.
Продолжить разбираться
Бесконечный спуск: почему меньших положительных решений не хватит
Разберите доказательство невозможности целочисленного решения: выберите положительную меру, сохраните уравнение и постройте строго меньшее решение.
Открыть темуКак контрпример отличает утверждение от обратного
Отличите прямое утверждение от обратного и подберите контрпример, который выполняет все условия, но нарушает проверяемый вывод.
Открыть тему