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

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

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

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

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

Шаг индукции — доказательство того, что из верности утверждения для n следует его верность для n + 1. В этом месте используют индукционное предположение и преобразуют выражение для нового случая. Так устанавливается связь между соседними значениями.

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

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

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

Затем формулируют индукционное предположение: считают утверждение верным для произвольного фиксированного n. Слово «произвольного» здесь существенно: доказательство должно работать для любого числа из диапазона, а не для выбранного примера вроде n = 5. Предположение временно принимают, чтобы исследовать, что из него следует для следующего случая.

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

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

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

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

Разбор задач

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

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

1. База: при n = 1 получаем 1 = 1·2/2 = 1, значит формула верна.
2. Предположим, что Sₙ = n(n + 1)/2. Тогда Sₙ₊₁ = Sₙ + (n + 1) = n(n + 1)/2 + (n + 1) = (n + 1)(n + 2)/2.
3. Последнее выражение равно формуле n(n + 1)/2, если вместо n поставить n + 1. Переход доказан.

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

Неравенство для степени двойки

Докажем, что 2ⁿ > n при всех натуральных n. При переходе степень удобно представить как 2ⁿ⁺¹ = 2 · 2ⁿ. Умножение на положительное число сохраняет знак строгого неравенства.

1. База: при n = 1 имеем 2¹ = 2 > 1.
2. Предположим, что 2ⁿ > n. Тогда 2ⁿ⁺¹ = 2 · 2ⁿ > 2n.
3. Для натурального n выполняется 2n ≥ n + 1, поэтому 2ⁿ⁺¹ > n + 1. Получили требуемый следующий случай.

Ответ: неравенство верно для всех натуральных n. Здесь одного индукционного предположения недостаточно без дополнительного сравнения 2n и n + 1. Это сравнение выполняется для каждого натурального n.

Делимость разности 7ⁿ − 1

Докажем, что 7ⁿ − 1 делится на 6 для всех натуральных n. Обозначение «делится на 6» означает, что выражение можно представить как 6, умноженное на целое число. Для перехода преобразуем выражение при n + 1 так, чтобы в нём появилась разность 7ⁿ − 1.

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

Ответ: 7ⁿ − 1 делится на 6 для всех натуральных n. Преобразование выделило выражение из предположения, а добавка 6 не нарушила делимость. Так доказан переход к следующему показателю.

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

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

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

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

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

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

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

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

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

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