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

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

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

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

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

Шаг индукции — доказательство того, что из P(k) следует P(k + 1). Здесь выражение или условие для следующего числа преобразуют так, чтобы использовать предположение P(k). Это показывает, как истинность утверждения передаётся от одного натурального числа к следующему.

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

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

Базу выбирают по условию: найдите наименьшее значение параметра, для которого утверждение вообще сформулировано. Затем подставьте его в обе части равенства, неравенства или условие делимости и проверьте результат. Если начать позже нужного значения, останется недоказанным начало диапазона; если взять недопустимое значение, проверка не будет относиться к задаче.

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

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

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

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

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

Разбор задач

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

1. База: при n = 1 левая часть равна 1, а правая — 1 · 2/2 = 1. Равенство верно, значит, цепочка индукции может начаться с единицы.
2. Предположим, что P(k) верно: 1 + 2 + … + k = k(k + 1)/2. Для следующего числа к сумме первых k чисел добавляется одно слагаемое k + 1, поэтому левая часть для P(k + 1) равна k(k + 1)/2 + k + 1.
3. Преобразуем: k(k + 1)/2 + k + 1 = (k + 1)(k + 2)/2. Это именно правая часть формулы при n = k + 1, следовательно, переход доказан.

Ответ. Равенство верно для всех натуральных n.

Задача. Докажите, что 7^n − 1 делится на 6 для любого натурального n. Обозначим утверждение о делимости через P(n). Для шага полезно представить степень с показателем k + 1 через степень с показателем k.

1. База: при n = 1 получаем 7 − 1 = 6, а 6 делится на 6.
2. Предположим, что 7^k − 1 делится на 6. Тогда 7^(k + 1) − 1 = 7 · 7^k − 1 = 7(7^k − 1) + 6. Первое слагаемое делится на 6 по предположению, второе делится на 6 без остатка.
3. Сумма двух чисел, делящихся на 6, также делится на 6. Значит, P(k + 1) верно, и переход от любого k к следующему выполнен.

Ответ. Число 7^n − 1 делится на 6 при каждом натуральном n.

Задача. Докажите, что 2^n > n + 1 при всех натуральных n ≥ 2. Здесь база отличается от единицы, потому что в условии указано ограничение n ≥ 2. В шаге нужно получить неравенство для k + 1 из предположения для k.

1. База: при n = 2 имеем 2² = 4, а 2 + 1 = 3, поэтому 4 > 3.
2. Предположим, что 2^k > k + 1, где k ≥ 2. Умножим обе части на положительное число 2: 2^(k + 1) > 2(k + 1).
3. Сравним правую часть с требуемой: 2(k + 1) ≥ k + 2, поскольку разность равна k и k ≥ 2. Значит, 2^(k + 1) > k + 2, то есть P(k + 1) верно.

Ответ. Неравенство верно для всех натуральных n ≥ 2.

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

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

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

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

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

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

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