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

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

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

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

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

Индукционный переход — доказательство того, что из истинности утверждения при n = k следует его истинность при n = k + 1. В этом шаге выражение для следующего номера связывают с выражением для k и используют индукционное предположение. Без такой связи переход не устанавливает нужную последовательность доказанных случаев.

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

Проверка нескольких первых случаев помогает заметить закономерность, но не доказывает её для всех натуральных чисел. Например, формула может совпадать с вычислениями при n = 1, 2 и 3, а нарушиться при большем значении. Исключить такой вариант можно только общим рассуждением, которое охватывает произвольный следующий номер.

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

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

В предположении разрешено временно считать верным только утверждение для произвольного k из рассматриваемого множества. Нельзя сразу принимать за верный случай k + 1: именно его требуется вывести. Чтобы не подменить доказательство, запишите отдельно: «Предположим, что при n = k …» и «Докажем, что при n = k + 1 …». Тогда видно, где используется допущение, а где выполняется доказательство.

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

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

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

Разбор задач

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

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

1. База: при n = 1 левая часть равна 1, а правая — 1 · 2/2 = 1. Начальный случай верен.

2. Предположение: пусть 1 + 2 + … + k = k(k + 1)/2 для некоторого натурального k. Для k + 1 левая часть равна 1 + 2 + … + k + (k + 1).

3. Переход: заменим сумму до k по предположению. Получаем k(k + 1)/2 + (k + 1) = (k + 1)(k + 2)/2, то есть формулу для n = k + 1.

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

Делимость выражения

Докажем, что 7ⁿ − 1 делится на 6 при каждом натуральном n. Идея перехода в том, чтобы выделить в выражении для k + 1 часть 7ᵏ − 1: её делимость уже будет известна из предположения. Проверим сначала, что утверждение запускается при n = 1.

1. База: 7¹ − 1 = 6, а 6 делится на 6.

2. Предположение: пусть 7ᵏ − 1 делится на 6 для некоторого натурального k. Значит, 7ᵏ − 1 = 6m для некоторого целого m.

3. Переход: 7ᵏ⁺¹ − 1 = 7(7ᵏ − 1) + 6 = 42m + 6 = 6(7m + 1). Полученное выражение делится на 6.

Ответ: 7ⁿ − 1 делится на 6 для каждого натурального n.

Неравенство с степенью

Докажем, что 2ⁿ > n + 1 при всех натуральных n ≥ 2. Здесь база начинается с 2, потому что именно с этого значения задано утверждение. При переходе удвоим левую часть и сравним полученную оценку с правой частью для следующего номера.

1. База: при n = 2 получаем 2² = 4 > 3 = 2 + 1.

2. Предположение: пусть 2ᵏ > k + 1 для некоторого k ≥ 2.

3. Переход: умножим неравенство на 2: 2ᵏ⁺¹ > 2(k + 1). Так как 2(k + 1) ≥ k + 2, то 2ᵏ⁺¹ > k + 2, что и требуется при n = k + 1.

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

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

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

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

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

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

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

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

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

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

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