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