§ 3.* Метод математической индукции

Определения и обозначения

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

База индукции — проверка утверждения для первого натурального значения, с которого начинается доказательство. Если условие имеет вид n ≥ 2, базой будет проверка при n = 2. Она нужна для запуска всей цепочки рассуждений.

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

Индукционный переход — доказательство того, что из истинности утверждения для n следует его истинность для n + 1. Обычно для этого преобразуют выражение, пользуясь предположением P(n). Такой шаг связывает каждый случай со следующим.

Как это устроено

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

Метод удобно сравнить с цепочкой домино. База подтверждает, что первое звено действительно падает, а индукционный переход показывает: падение любого звена приводит в движение следующее. Значит, после первого падут все последующие звенья, как после P(n) становится верным P(n + 1).

Сначала формулируют утверждение P(n) и указывают область допустимых n. Затем выбирают начальное значение n₀ и проверяют P(n₀) непосредственно. Такая запись заранее показывает, с какого места начинается цепочка и какой именно результат требуется доказать.

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

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

Этапы доказательства методом математической индукции

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

Разбор задач

1. Сумма нечётных чисел

Условие: докажите, что 1 + 3 + 5 + … + (2n − 1) = n² для всех n ≥ 1. Обозначим это равенство через P(n). В переходе нужно добавить к сумме для n следующее нечётное число.

1. База: при n = 1 левая часть равна 1, а правая — 1² = 1, значит, P(1) верно.
2. Предположение: пусть 1 + 3 + … + (2n − 1) = n².
3. Переход: добавим число 2(n + 1) − 1 = 2n + 1. Получим 1 + 3 + … + (2n + 1) = n² + 2n + 1 = (n + 1)².

Ответ: база и переход доказаны, поэтому равенство верно для всех n ≥ 1.

2. Делимость

Условие: докажите, что 7ⁿ − 1 делится на 6 для всех n ≥ 1. Здесь удобно представить выражение для следующей степени через выражение, известное из предположения. Это позволит сразу увидеть множитель 6.

1. База: 7¹ − 1 = 6, а 6 делится на 6.
2. Предположение: пусть 7ⁿ − 1 делится на 6.
3. Переход: 7ⁿ⁺¹ − 1 = 7 · 7ⁿ − 1 = 7(7ⁿ − 1) + 6. Оба слагаемых делятся на 6, значит, делится и вся сумма.

Ответ: 7ⁿ − 1 делится на 6 при каждом n ≥ 1.

3. Неравенство

Условие: докажите, что 2ⁿ > n + 1 для всех n ≥ 2. Начинать нужно с n = 2, потому что именно с этого значения дано утверждение. В переходе потребуется умножить предположение на 2.

1. База: 2² = 4 > 3 = 2 + 1, поэтому P(2) верно.
2. Предположение: пусть 2ⁿ > n + 1.
3. Переход: 2ⁿ⁺¹ = 2 · 2ⁿ > 2(n + 1) = 2n + 2. При n ≥ 2 имеем 2n + 2 > n + 2, следовательно, 2ⁿ⁺¹ > n + 2.

Ответ: неравенство доказано для всех n ≥ 2.

Типичные ошибки

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

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

В переходе нельзя использовать уже доказанное P(n + 1), поскольку именно его ещё требуется получить. Иногда это маскируют фразой «очевидно, что следующий случай верен». Проверь каждое преобразование: оно должно опираться только на P(n), условия задачи и известные свойства.

Записать переход без связи P(n) и P(n + 1) недостаточно. Если просто выписаны два похожих выражения, читатель не видит, как предположение помогает доказательству. Полезно отдельно отметить формулу P(n), затем преобразовать её к виду P(n + 1).

Связь с другими темами

До изучения метода нужны навыки преобразования алгебраических выражений и работы с натуральными числами. Также пригодятся свойства делимости: если два числа делятся на 6, то их сумма тоже делится на 6. Без этих приёмов индукционный переход будет трудно оформить.

Метод применяют к формулам сумм, неравенствам и утверждениям о делимости, зависящим от натурального параметра. Он связывает отдельные темы алгебры общей схемой доказательства. Поэтому умение видеть структуру P(n) и P(n + 1) помогает решать разные по виду задачи.

Что запомнить

• Сначала сформулируй утверждение P(n) и укажи, для каких n его доказываешь.
• База индукции проверяет начальное значение.
• В переходе предполагай P(n) и доказывай P(n + 1).
• Предположение индукции — временное допущение внутри перехода, а не уже доказанное утверждение для всех n.
• База вместе с переходом позволяет заключить, что утверждение верно для всех n начиная с начального значения.
• Проверка нескольких частных случаев сама по себе не является доказательством.