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

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

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

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

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

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

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

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

Сначала записывают утверждение, обычно обозначая его P(n), и точно определяют, при каких n оно должно быть верным. Затем проверяют базу, подставляя начальное значение. После этого выбирают произвольное k из области утверждения, принимают P(k) как временное условие и доказывают P(k + 1). Такое разделение не даёт спутать проверку одного случая с доказательством общего правила.

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

Начальный номер выбирают по области, где сформулировано утверждение. Если оно заявлено для всех натуральных n, база обычно проверяет n = 1; если только для n ≥ 5, проверять нужно n = 5. Проверка неподходящего номера не запускает нужную цепочку: переход от него может не охватить первую часть области или вообще не соответствовать условию задачи.

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

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

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

Разбор задач

Задача 1. Доказать, что 1 + 3 + 5 + … + (2n − 1) = n² для любого натурального n.

1. Обозначим сумму первых n нечётных чисел через P(n). При n = 1 левая часть равна 1, правая тоже равна 1² = 1, значит база верна.

2. Пусть для произвольного k верно P(k): сумма первых k нечётных чисел равна k². Для случая k + 1 к этой сумме добавляется следующий нечётный член 2(k + 1) − 1 = 2k + 1.

3. Тогда новая сумма равна k² + 2k + 1 = (k + 1)². Это и есть правая часть формулы для k + 1, поэтому переход доказан. Ответ: равенство верно для всех натуральных n.

Задача 2. Доказать, что 7ⁿ − 1 делится на 6 для любого натурального n.

1. При n = 1 получаем 7 − 1 = 6, а 6 делится на 6. Это база. Пусть теперь для произвольного k число 7ᵏ − 1 делится на 6.

2. Рассмотрим следующий показатель и разложим выражение: 7ᵏ⁺¹ − 1 = 7 · 7ᵏ − 1 = 7(7ᵏ − 1) + 6. В скобках стоит число, делящееся на 6 по предположению, значит и 7(7ᵏ − 1) делится на 6.

3. К нему прибавлено 6, поэтому вся сумма делится на 6. Так доказан переход от k к k + 1. Ответ: 7ⁿ − 1 делится на 6 при любом натуральном n.

Задача 3. Доказать, что 2ⁿ > n² при всех натуральных n ≥ 5.

1. Проверим базу при n = 5: 2⁵ = 32, а 5² = 25, поэтому 32 > 25. Пусть для некоторого k ≥ 5 верно 2ᵏ > k².

2. Умножив обе части на 2, получим 2ᵏ⁺¹ > 2k². Чтобы из этого следовало 2ᵏ⁺¹ > (k + 1)², достаточно установить 2k² ≥ (k + 1)².

3. Разность равна 2k² − (k + 1)² = k² − 2k − 1. При k ≥ 5 она положительна: k² − 2k − 1 ≥ 25 − 10 − 1 = 14. Значит, нужное сравнение верно и переход доказан. Ответ: неравенство выполняется для всех n ≥ 5.

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

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

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

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

Можно забыть базу или проверить число, не входящее в область утверждения. Тогда переходу не от чего начинать либо доказательство не охватывает нужные значения. Перед завершением сравните базу с условием задачи: если n ≥ 5, проверьте n = 5, а не n = 1, и отдельно убедитесь, что переход применим при всех k не меньше начального.

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

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

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

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

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

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