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

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

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

База индукции — проверка утверждения для первого значения натурального параметра. Если отсчёт начинается с единицы, проверяют P(1), а если с двух — P(2). База подтверждает первое звено цепочки, от которого начинается дальнейшее доказательство.

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

Индукционный переход — доказательство истинности утверждения для k + 1 из его истинности для k. Нужно показать: если P(k) верно, то верно и P(k + 1). Именно переход связывает соседние значения и переносит доказательство на всю цепочку натуральных чисел.

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

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

Утверждение записывают как P(n), где n принимает натуральные значения. Затем отдельно подставляют первое допустимое число: например, при P(n) для всех n ≥ 1 проверяют P(1), а при условии n ≥ 2 — P(2). Такая проверка устанавливает точку старта и одновременно уточняет область действия утверждения.

В переходе временно предполагают истинность P(k), потому что нужно выяснить, сохраняется ли утверждение при увеличении параметра на единицу. Это предположение не выдают за уже доказанную формулу для всех чисел. Оно используется только как условие рассуждения: при его выполнении надо получить P(k + 1).

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

База показывает истинность первого случая, а переход передаёт её следующему: от P(1) к P(2), затем к P(3) и так далее. Один переход без базы не доказывает ничего для конкретного начала, поскольку неизвестно, есть ли первое верное звено. Поэтому только соединение базы и перехода даёт утверждение для всех рассматриваемых натуральных n.

Схема доказательства методом математической индукции

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

Если какой-либо этап пропущен, логическая цепочка становится неполной. Особенно нельзя заменять индукционное предположение готовым утверждением для следующего значения. Запись этапов помогает увидеть, где используется условие P(k), а где появляется новый результат.

Разбор задач

Задача 1. Сумма первых натуральных чисел

Условие: доказать, что 1 + 2 + 3 + … + n = n(n + 1)/2 для любого натурального n. Обозначим это утверждение через P(n). Начальное значение — n = 1.

1. База: 1 = 1·(1 + 1)/2 = 1, поэтому P(1) верно.
2. Предположим, что 1 + 2 + … + k = k(k + 1)/2.
3. Добавим к обеим частям k + 1: 1 + … + k + (k + 1) = k(k + 1)/2 + k + 1 = (k + 1)(k + 2)/2.
4. Последнее выражение совпадает с формулой для k + 1, значит переход выполнен.

Ответ: формула доказана для всех натуральных n. В переходе использовано именно предположение для k, после чего к сумме добавлено новое слагаемое.

Задача 2. Степень двойки и натуральное число

Условие: доказать, что 2ⁿ > n для всех натуральных n, начиная с n = 2. Здесь P(n) означает неравенство 2ⁿ > n. Базой будет n = 2.

1. База: 2² = 4 > 2, поэтому P(2) верно.
2. Предположим, что 2ᵏ > k для некоторого k ≥ 2.
3. Умножим на 2: 2ᵏ⁺¹ > 2k. Так как k ≥ 2, имеем 2k ≥ k + 1.
4. Следовательно, 2ᵏ⁺¹ > k + 1, то есть верно P(k + 1).

Ответ: неравенство доказано для всех n ≥ 2. Дополнительное условие k ≥ 2 нужно, чтобы сравнить 2k и k + 1.

Задача 3. Сумма квадратов

Условие: доказать, что 1² + 2² + … + n² = n(n + 1)(2n + 1)/6. Обозначим формулу через P(n) и начнём с n = 1. В переходе появится новое слагаемое (k + 1)².

1. База: 1² = 1·2·3/6 = 1.
2. Предположим, что 1² + … + k² = k(k + 1)(2k + 1)/6.
3. Прибавим (k + 1)² и вынесем k + 1: (k + 1)[k(2k + 1)/6 + k + 1].
4. Приведение к общему знаменателю даёт (k + 1)(k + 2)(2k + 3)/6 — формулу для k + 1.

Ответ: формула верна для любого натурального n. Главная идея состоит в том, чтобы использовать выражение для первых k квадратов и включить в сумму следующий квадрат.

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

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

Сразу используют формулу для k + 1. Это подмена доказательства требуемым результатом: запись выглядит правдоподобно, но связь с P(k) не показана. Проверь, откуда получено каждое преобразование и где применено предположение.

Забывают базу или выбирают неверное начало. Если утверждение начинается с n ≥ 2, проверка P(1) не заменяет базу P(2). Сверь начальное значение с условием задачи и подставь его в обе части утверждения.

Доказывают P(k) из P(k + 1). Такое рассуждение идёт в обратную сторону и не передаёт истинность от меньшего числа к большему. Проверь направление: целью перехода должна быть запись для k + 1, а исходным условием — P(k).

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

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

Метод особенно полезен для формул сумм, неравенств, признаков делимости и утверждений о последовательностях. Он позволяет заменять бесконечную проверку общей логической схемой.

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

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

• Индукционное доказательство состоит из базы и индукционного перехода.
• В базе проверяют утверждение для первого допустимого значения.
• В индукционном предположении утверждение считают верным для произвольного k.
• В переходе доказывают истинность утверждения для k + 1.
• Индукционное предположение разрешено использовать только внутри индукционного перехода.
• После доказательства базы и перехода утверждение верно для всех рассматриваемых натуральных n.