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

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

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

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

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

Индукционный переход — доказательство верности утверждения для n + 1 при условии его верности для n. Он связывает соседние значения и позволяет перенести истинность на весь ряд натуральных чисел.

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

Сначала нужно указать множество натуральных чисел и начальное значение параметра. Без этого непонятно, с какого случая начинается доказательство и для каких именно n требуется результат. Например, утверждение может быть верно для всех n ≥ 1 или только для n ≥ 5.

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

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

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

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

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

Таблицу удобно использовать как чек-лист при записи решения. Если пропущена база или не показана связь между n и n + 1, доказательство остаётся незавершённым.

Разбор задач

Задача 1. Формула суммы

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

1. При n = 1 левая часть равна 1, а правая — 1 · 2/2 = 1. База выполнена.
2. Пусть P(n) верно: 1 + 2 + … + n = n(n + 1)/2.
3. Тогда 1 + 2 + … + n + (n + 1) = n(n + 1)/2 + n + 1 = (n + 1)(n + 2)/2. Это формула P(n + 1).

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

Задача 2. Делимость

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

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

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

Задача 3. Неравенство

Условие: доказать, что 2ⁿ > n² для всех натуральных n, начиная с n = 5. Начальное значение не равно единице, поэтому базу нужно проверять именно с n = 5.

1. При n = 5 имеем 2⁵ = 32 > 25 = 5². База выполнена.
2. Пусть для некоторого n ≥ 5 верно 2ⁿ > n².
3. Умножая на 2, получаем 2ⁿ⁺¹ > 2n². Кроме того, 2n² ≥ (n + 1)², поскольку n² − 2n − 1 ≥ 0 при n ≥ 5. Следовательно, 2ⁿ⁺¹ > (n + 1)².

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

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

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

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

Использование утверждения для n + 1 без вывода. Нельзя просто написать нужную формулу как очевидную. Раскройте выражение для n + 1 и покажите, где именно применено предположение для n.

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

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

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

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

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