"Алгебра и начала математического анализа (базовый и углубленный уровень) (в 2 частях), изд-во «Мнемозина»", Мордкович А.Г.
Метод математической индукции позволяет доказать утверждение сразу для всех натуральных чисел, начиная с заданного значения. Для этого проверяют утверждение при первом допустимом n, а затем показывают: если оно верно для произвольного k, то верно и для k + 1. База запускает доказательство, а переход связывает соседние значения. Метод применяют к формулам сумм, делимости и неравенствам.
Текст подготовлен нейронной сетью по теме параграфа и не заменяет учебник — важные факты и формулировки сверяйте с ним.
Высказывание P(n) — утверждение, зависящее от натурального числа n. Для каждого допустимого значения подставляют n и выясняют, получается ли верное утверждение, например равенство или неравенство. Обозначение P(n) помогает кратко записать, какое именно утверждение доказывают.
База индукции — проверка утверждения P(n) для начального значения n₀, с которого начинается доказательство. Нужно подставить именно это число и установить, что утверждение верно. База необходима, чтобы индукционное рассуждение имело отправную точку.
Предположение индукции — допущение, что P(k) верно для произвольного фиксированного k ≥ n₀. Число k не выбирают заранее как конкретное: рассуждение должно подходить для любого такого k. Это допущение используют только для доказательства утверждения при следующем числе.
Индукционный переход — доказательство того, что из P(k) следует P(k + 1) для любого k ≥ n₀. В ходе перехода выражение для k + 1 преобразуют, используя предположение P(k). Так проверка одного начального случая становится основой для доказательства следующих.
Принцип математической индукции таков: если P(n₀) верно и для любого k ≥ n₀ из P(k) следует P(k + 1), то P(n) верно для всех n ≥ n₀. База подтверждает первый случай. Переход обеспечивает верность следующего случая при условии, что верен предыдущий. Поэтому вместе они охватывают всю область натуральных чисел, начиная с n₀.
Это можно представить как цепочку: каждое число связано со следующим. База запускает цепочку, а переход показывает, что звено с номером k передаёт истинность звену с номером k + 1. Если проверить только базу, дальнейшие звенья не подтверждены; если доказать переход без базы, неизвестно, с чего начинать. Нужны оба шага.
Сначала записывают P(n), чтобы точно видеть доказываемое утверждение, и указывают область значений n. Затем проверяют базу при n = n₀. После этого формулируют предположение: пусть P(k) верно для произвольного k ≥ n₀. Используя его, выводят P(k + 1) и в конце указывают, для каких n получен результат.
В переходе нельзя просто принять P(k + 1) за верное: это как раз то, что требуется доказать. Нужно взять выражение или условие для следующего случая и преобразовать его так, чтобы использовать P(k). Например, в сумме добавляют следующий член, а при доказательстве делимости выделяют выражение, делящееся на заданное число. Такой вывод и составляет основную работу перехода.
Начальное значение и допустимая область n задаются условием задачи. Если утверждение требуется для n ≥ 2, проверка только при n = 1 не будет подходящей базой, даже если равенство или неравенство там верно. Иногда условие начинает отсчёт с нуля, а иногда — с единицы или другого числа. Базу выбирают так, чтобы она совпадала с началом требуемой области.
| Этап | Что записать или проверить | Зачем это нужно |
|---|---|---|
| Формулировка P(n) | Точное утверждение и допустимые значения n | Чтобы ясно обозначить, что доказывается |
| База индукции при n = n₀ | Подстановку начального значения и проверку | Чтобы запустить доказательство |
| Предположение индукции для n = k | Утверждение P(k) для произвольного k ≥ n₀ | Чтобы использовать его в переходе |
| Переход от P(k) к P(k + 1) | Вывод утверждения для следующего числа | Чтобы связать соседние случаи |
| Вывод для всех n ≥ n₀ | Итог с указанием всей области | Чтобы завершить доказательство |
Используйте таблицу как порядок проверки: не переходите к следующему этапу, пока не выполнен предыдущий. Особенно внимательно проверьте, что в переходе получено именно P(k + 1), а не только проведены преобразования для P(k). В заключении укажите начальное значение и все n, для которых доказано утверждение.
Задача. Докажите, что 1 + 2 + ... + n = n(n + 1)/2 для всех натуральных n. Обозначим это равенство через P(n). Идея перехода — прибавить к сумме для k следующий член k + 1 и преобразовать результат.
База. При n = 1 левая часть равна 1, а правая — 1 · 2/2 = 1. Значит, P(1) верно, и доказательство можно продолжать от первого натурального числа.
Предположение. Пусть для произвольного k ≥ 1 верно 1 + 2 + ... + k = k(k + 1)/2. Это равенство можно подставить вместо суммы первых k чисел при проверке следующего случая.
Переход. Для k + 1 получаем 1 + 2 + ... + k + (k + 1). По предположению это равно k(k + 1)/2 + (k + 1) = (k + 1)(k + 2)/2, то есть формуле для n = k + 1.
Ответ: равенство верно для всех натуральных n по принципу математической индукции.
Задача. Докажите, что 7ⁿ − 1 делится на 6 для всех натуральных n. Здесь P(n) означает, что выражение 7ⁿ − 1 кратно 6. В переходе удобно использовать равенство 7ᵏ⁺¹ − 1 = 7(7ᵏ − 1) + 6.
База. При n = 1 имеем 7¹ − 1 = 6, а это делится на 6. Следовательно, P(1) верно.
Предположение. Пусть 7ᵏ − 1 делится на 6 для произвольного k ≥ 1. Тогда 7(7ᵏ − 1) также делится на 6, поскольку умножение кратного 6 на целое число сохраняет делимость на 6.
Переход. Запишем 7ᵏ⁺¹ − 1 = 7(7ᵏ − 1) + 6. Оба слагаемых справа делятся на 6, значит, их сумма тоже делится на 6, и P(k + 1) верно.
Ответ: 7ⁿ − 1 делится на 6 при каждом натуральном n.
Задача. Докажите, что 2ⁿ > n + 1 для всех натуральных n ≥ 2. В переходе нужно получить оценку для k + 2 из предположения 2ᵏ > k + 1. Умножение обеих частей на положительное число 2 сохраняет знак неравенства.
База. При n = 2 имеем 2² = 4, а 2 + 1 = 3, поэтому 4 > 3. Утверждение верно при начальном значении.
Предположение. Пусть для произвольного k ≥ 2 верно 2ᵏ > k + 1. Умножая обе части на 2, получаем 2ᵏ⁺¹ > 2k + 2.
Переход. Так как k ≥ 2, то 2k + 2 ≥ k + 2. Поэтому 2ᵏ⁺¹ > k + 2, что и есть требуемое неравенство при n = k + 1.
Ответ: неравенство верно для всех натуральных n ≥ 2.
Проверить несколько первых значений и объявить утверждение доказанным — ошибка, потому что примеры подтверждают его лишь для конкретных n. Так делают, когда закономерность кажется очевидной, но дальше она может нарушиться. Для проверки себя спросите: доказан ли переход для произвольного k?
Не указать начальное значение или выбрать его неверно — значит, оставить базу вне требуемой области. Ошибка возникает, если не сверить начало доказательства с условием задачи. Проверьте, что при n₀ утверждение требуется и действительно верно.
Принять P(k + 1) без вывода — значит, пропустить главный шаг доказательства. Это часто происходит, когда нужная формула для следующего числа уже видна, и её записывают как готовый факт. Проверьте, выведено ли P(k + 1) из P(k) преобразованиями или рассуждением.
Сформулировать предположение для одного конкретного числа недостаточно, потому что переход должен работать для каждого k из нужной области. Конкретный пример проверяет лишь один переход и не гарантирует остальные. Убедитесь, что k выбран произвольно и в рассуждении используются только условия k ≥ n₀.
Для метода нужны понятия натурального числа и математического высказывания: без них нельзя точно указать область n и сформулировать P(n). При доказательстве также используются делимость, равенства и неравенства. Умение преобразовывать алгебраические выражения помогает связать случай k + 1 с предположением для k.
Индукцией доказывают формулы для сумм и последовательностей, утверждения о делимости и неравенства. Тот же принцип встречается в комбинаторике и последующих математических курсах. Если задача содержит утверждение для каждого натурального n, индукцию стоит рассмотреть как возможный способ доказательства.
Почему проверки нескольких первых значений недостаточно?
Проверка нескольких чисел подтверждает утверждение только для этих чисел. Дальше оно может перестать быть верным, поэтому для всех n нужен доказанный переход от k к k + 1.
Можно ли начать доказательство с n = 0?
Можно, если по условию утверждение рассматривается при n ≥ 0 и выражения имеют смысл при n = 0. Тогда базой будет проверка P(0), а переход доказывают для всех k ≥ 0.
Что именно можно считать верным в предположении индукции?
Только утверждение P(k) для произвольного фиксированного k из заданной области. P(k + 1) заранее верным считать нельзя: его требуется вывести из предположения.
Как понять, что выбрать базой индукции?
Базой служит наименьшее значение n, с которого требуется доказать утверждение. Его задаёт условие задачи; при необходимости начальных значений может быть несколько.
Почему доказательство перехода от k к k + 1 охватывает все натуральные числа?
После проверки базы переход доказывает утверждение для следующего числа. Применяя его снова, получаем все дальнейшие значения: база и переход образуют непрерывную цепочку.
§ 6. Метод математической индукции
